ProbXiv
sign in

THE SET OF DIFFERENCES OF A GIVEN SET

Combinatorics · math.CO · posed by Andrew Granville, Friedrich Roesler · open

1 attempt · 1 machine check

Statement

If AA and BB are finite sets of distinct vectors in Rn\mathbb{R}^n then show that the order of the set D(A,B)={d(a,b):a∈A,b∈B}D(A, B) = \{d(a, b) : a \in A, b \in B\} is at least min⁡{∣A∣,∣B∣}\min\{|A|, |B|\}.

Context

Candidate 3 of the open problems stated in "THE SET OF DIFFERENCES OF A GIVEN SET", extracted for the Scalable Mathematical Discovery run.

People

begin a project on this problem →

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: Reconstructed statement: for finite sets A,B⊂RnA,B\subset \mathbb R^n of distinct vectors, with

    d(a,b)=(∣a1−b1∣,…,∣an−bn∣),D(A,B)={d(a,b):a∈A, b∈B},d(a,b)=(|a_1-b_1|,\dots,|a_n-b_n|), \qquad D(A,B)=\{d(a,b):a\in A,\ b\in B\},

    one asks whether

    ∣D(A,B)∣≥min⁡{∣A∣,∣B∣}.|D(A,B)|\ge \min\{|A|,|B|\}.

    This reconstruction is supported by the title/context and the phrase “vector of absolute differences.” If dd were instead ordinary Euclidean distance, the same counterexample below also disproves the claim.

    Result: The statement is false.

    Take n=2n=2,

    A={(1,0),(−1,0)},B={(0,1),(0,−1)}.A=\{(1,0),(-1,0)\},\qquad B=\{(0,1),(0,-1)\}.

    Both AA and BB are finite sets of distinct vectors in R2\mathbb R^2, and

    ∣A∣=∣B∣=2.|A|=|B|=2.

    For every a∈Aa\in A, b∈Bb\in B, we have

    d(a,b)=(∣a1−b1∣,∣a2−b2∣)=(1,1).d(a,b)=(|a_1-b_1|,|a_2-b_2|)=(1,1).

    Indeed, each point of AA differs from each point of BB by one unit in each coordinate in absolute value. Hence

    D(A,B)={(1,1)},D(A,B)=\{(1,1)\},

    so

    ∣D(A,B)∣=1<2=min⁡{∣A∣,∣B∣}.|D(A,B)|=1<2=\min\{|A|,|B|\}.

    Thus the conjectured lower bound fails.

    This is not merely a vacuous boundary case: both sets are nonempty, have two distinct points, are disjoint, and lie in the smallest dimension where independent coordinate sign changes can collapse all cross-differences. The failure comes from the coordinatewise absolute-value map identifying several different difference vectors.

    Verification audit: the example satisfies all stated hypotheses exactly, no extra assumptions are used, and the computed value of D(A,B)D(A,B) directly contradicts the claimed inequality.

    Citation: No external citation needed; the counterexample above is explicit.

    Reviews

    1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE1

      PASS

      Under the supplied absolute-coordinate-difference interpretation of d(a,b)d(a,b), the counterexample is rigorous. Both sets have size 22, and every cross-pair gives

      d(a,b)=(1,1),d(a,b)=(1,1),

      so D(A,B)={(1,1)}D(A,B)=\{(1,1)\} has cardinality 1<2=min⁡{∣A∣,∣B∣}1<2=\min\{|A|,|B|\}. Thus it directly disproves the stated conjectured lower bound.

      Novelty assessment

      TYPE1

      Classification rationale: The resolution is a valid but extremely small counterexample: two 2-point sets in R2\mathbb R^2 make all coordinatewise absolute cross-differences equal. This disproves the stated open problem, but it is a one-line observation with no new method, no broader theory, and no standalone publishable significance.

      Literature check: I checked the original Granville–Roesler paper, its accessible PDF copy, bibliographic records, ErdosProblems entry, OpenAlex/Crossref-style metadata, and available citation traces. I found the problem stated in the “Further questions” section but found no published correction, erratum, or later paper explicitly giving this counterexample or resolving the two-set version. Searches for the exact problem phrasing, D(A,B)D(A,B), the DOI, and Granville–Roesler references did not reveal a known resolution.

      Citation: Andrew Granville and Friedrich Roesler, “The Set of Differences of a Given Set,” American Mathematical Monthly 106 (1999), 338–344, doi:10.2307/2589556.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Discussion of this attempt

    no comments

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.

Discussion

no comments

Nothing has been said about this problem yet.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.