PROJECTING DIFFERENCE SETS ON THE POSITIVE ORTHANT

RON HOLZMAN, VSEVOLOD F. LEV, AND ROM PINCHASI

Abstract. Let n ≥ 1 be an integer. Given a vector a = (a_{1}, …, a_{n}) ∈ ℝ^{n}, write a^{+} := (max{a_{1}, 0}, …, max{a_{n}, 0}) (the “projection of a onto the positive orthant”). For a set A ⊆ ℝ^{n} put A^{+} := {a^{+} : a ∈ A} and A−A := {a−b: a, b ∈ A}. Improving previously known bounds, we show that |(A − A)^{+}| ≥ |A|^{3/5}/6 for any finite set A ⊆ ℝ^{3}, and that |(A − A)^{+}| ≥ c|A|^{6/11}/(log |A|)^{2/11} with an absolute constant c > 0 for any finite set A ⊆ ℝ^{4} such that |A| ≥ 2.

1. Introduction

In connection with a well-known conjecture by Graham (solved by Balasubramanian and Soundararajan in [BS96]), Granville and Roesler raised in [GR99] the following problem: for a finite set A of positive integers with prescribed cardinality |A|, how small can be the set

\{\frac{a}{gcd(a,b)} : a, b ∈ A\} ?

As indicated in [GR99], this question can be equivalently re-stated as a combinatorial geometry problem, closely resembling the famous Erdős distance problem. Specifically, for a real number x let x^{+} := max{x, 0}. Given an integer n ≥ 1, for a vector a = (a_{1}, …, a_{n}) ∈ ℝ^{n} write

a^{+} := (a_{1}^{+}, …, a_{n}^{+}),

and for a set A ⊆ ℝ^{n} put

A^{+} := {a^{+} : a ∈ A}

and

A − A := {a − b: a, b ∈ A}.

How small can |(A − A)^{+}| be for a finite set A ⊆ ℝ^{n} of the given size |A|? There are two notable special cases in which the inequality

|(A − A)^{+}| ≥ |A|  (1)

holds true. First, it is easily seen to hold for n = 1; that is, when A is a set of real numbers. The estimate of (1) is sharp in this case: equality is attained if A is an

2 RON HOLZMAN, VSEVOLOD F. LEV, AND ROM PINCHASI

arithmetic progression. Secondly, (1) holds if A ⊆ {0, 1}^{n}; in this case the elements of A can be associated with subsets of an n-element set, and (A − A)^{+} corresponds then to the family of all set-theoretic differences of these subsets. In this form the problem was studied in [MS69] by Marica and Schönheim. Their result says that the number of differences is at least as large as the number of subsets, which is equivalent to (1). Here, too, the estimate is sharp, as it follows by considering a family of sets that is closed under taking subsets.

Though (1) fails in general, it was observed by the authors of [GR99] and independently by Noga Alon (personal communication) that the simple universal bound |(A − A)^{+}| ≥ \sqrt{|A|} is true for any dimension n and any finite set A ⊆ ℝ^{n}. This follows from the identity

x = x^{+} − (−x)^{+}; x ∈ ℝ,

which shows that a − b = (a − b)^{+} − (b − a)^{+} for any a, b ∈ A, leading to |A − A| ≤ |(A − A)^{+}|^{2} and immediately implying the estimate in question.

A refined bound for n = 2 was obtained in [GR99].

Theorem 1 ([GR99]). If A ⊆ ℝ^{2} is finite, then |(A − A)^{+}| ≥ (|A|/2)^{2/3}.

An example due to Freiman and one of the present authors (see [GR99]) shows that the estimate of Theorem 1 is of the best possible order; indeed, if m is a positive integer and A is the set of integer vectors (x_{1}, x_{2}) with positive coordinates, satisfying |(x_{1} + x_{2}) − (2m)^{2/3}/2| < (2m)^{1/3}/2, then |A| = m(1 + o(1)) and |(A − A)^{+}| = \frac{3}{2}(2m)^{2/3}(1 + o(1)).

Clearly, the example just given can be “lifted” to any dimension n ≥ 2, showing that

\sqrt{m} ≤ min_{A⊆ℝ^{n}: |A|=m}|(A − A)^{+}| ≤ \frac{3}{2}(2m)^{2/3}(1 + o(1))

as m → ∞, uniformly in n. The challenging open problem is to close the gap between the bounds, or at least to determine whether there exist positive absolute constants δ > 0.5 and c > 0 such that |(A − A)^{+}| ≥ c|A|^{δ} holds for any n ≥ 1 and any finite set A ⊆ ℝ^{n}. By all we know, it is even possible that δ = 2/3 will do.

In this paper we improve the “universal bound” for 3-dimensional and 4-dimensional sets.

Theorem 2. If A ⊆ ℝ^{3} is finite, then |(A − A)^{+}| ≥ \frac{1}{6} |A|^{3/5}.

Theorem 3. There is an absolute constant c > 0 such that if A ⊆ ℝ^{4} is finite and |A| ≥ 2, then |(A − A)^{+}| ≥ c|A|^{6/11}/(log |A|)^{2/11}.

PROJECTING DIFFERENCE SETS 3

We notice that our proof of Theorem 2 actually leads to a factor slightly larger than 1/6, and that further minor improvements are possible without modifying the proof substantially. The proof of Theorem 3 allows one to explicitly compute the constant c appearing in the statement of the theorem.

Theorems 2 and 3 are proved in Sections 3 and 4, respectively. An important auxiliary estimate, relating the size of (A − A)^{+} with those of the projections of A onto the coordinate hyperplanes, is established in the next section.

2. Positive differences and projections

Let n ≥ 1 be an integer. For i ∈ [1, n] we let

P_{i} := {(x_{1}, …, x_{n}) ∈ ℝ^{n}: x_{i} = 0}

(the ith coordinate hyperplane), and

L_{i} := {(x_{1}, …, x_{n}) ∈ ℝ^{n}: x_{j} = 0 for j ∈ [1, n], j ≠ i}

(the ith coordinate axis). Given a set A ⊆ ℝ^{n}, by A_{i} we denote the orthogonal projection of A onto P_{i}.

We start with a very basic, but useful observation.

Lemma 1. If n ≥ 2 is an integer and A ⊆ ℝ^{n} is finite, then |(A−A)^{+}| ≥ |(A_{i}−A_{i})^{+}| holds for any i ∈ [1, n].

Proof. Since (B_{i})^{+} = (B^{+})_{i} for any B ⊆ ℝ^{n}, we have

|(A_{i} − A_{i})^{+}| = |((A − A)_{i})^{+}| = |((A − A)^{+})_{i}| ≤ |(A − A)^{+}|.
□

The next lemma is our main tool.

Lemma 2. If n ≥ 2 is an integer and A ⊆ ℝ^{n} is a non-empty finite set, then

|(A − A)^{+}| ≥ \frac{1}{n^{n}} \frac{|A|^{n}}{|A_{1}| ⋯ |A_{n}|}.

Proof. For each i ∈ [1, n] set k_{i} := ⌈|A|/(n|A_{i}|)⌉ − 1. There are |A_{n}| lines in ℝ^{n}, parallel to L_{n} and passing through a point of A. On each of these lines find k_{n} points of A with the largest nth coordinate and remove them from A, passing to a new set A^{(n−1)} ⊆ ℝ^{n}. (If a line contains fewer than k_{n} points of A, remove them all.) The number of removed points is at most k_{n}|A_{n}|, and hence |A^{(n−1)}| > (1 − 1/n)|A|. Now consider the lines in ℝ^{n}, parallel to L_{n−1} and passing through the points of A^{(n−1)}, and remove from A^{(n−1)} those points which are among the k_{n−1} “highest” on their lines. This yields a new set A^{(n−2)}, and since the total number of lines, considered at the second step, is at most |A_{n−1}|, we have |A^{(n−2)}| > (1 − 2/n)|A|. Repeating this procedure, after n steps we get a non-empty set A^{(0)} ⊆ A. Fix arbitrarily a_{0} ∈ A^{(0)}. Since a_{0} was not removed at the nth step, there are at least k_{1} + 1 points in A^{(1)} which coincide with a_{0} in all but the first coordinate, and whose first coordinate is at least as large as that of a_{0}. Similarly, to each of these k_{1} + 1 points in A^{(1)} there correspond at least k_{2} + 1 points in A^{(2)} which coincide with the original point in all coordinates but the second one, and whose second coordinates are greater than or equal to that of the original point. Continuing in this way, we eventually find at least

(k_{1} + 1) ⋯ (k_{n} + 1) ≥ \frac{1}{n^{n}} \frac{|A|^{n}}{|A_{1}| ⋯ |A_{n}|}

points in A which are greater than or equal to a_{0} in each coordinate. Subtracting a_{0} from each of these points we obtain the required number of pairwise distinct points in A − A with non-negative coordinates, and the result follows. □

We remark that the proof of Lemma 2 can easily be modified to show that any finite set A ⊆ ℝ^{n} contains Ω (\frac{|A|^{n+1}}{|A_{1}|···|A_{n}|}) comparable pairs of points (that is, pairs (a, b) such that all coordinates of a − b are of the same sign).

Notice also that using Lemma 2 one can easily obtain an alternative proof of Theorem 1. Namely, if A ⊆ ℝ^{2} is finite and non-empty, then |(A−A)^{+}| ≥ |A|^{2}/(4|A_{1}||A_{2}|) by Lemma 2, and furthermore |(A − A)^{+}| ≥ |A_{1}| and |(A − A)^{+}| ≥ |A_{2}| by Lemma 1. Multiplying out these estimates, we get |(A − A)^{+}| ≥ (|A|/2)^{2/3}, as required.

3. 3-dimensional sets: proof of Theorem 2

We first translate A so that 0 ∈ A and all points of A have non-negative third coordinate. There is then a coordinate octant O, containing at least |A|/4 points of A. Choose a two-element set {i, j} ⊆ [1, 3] so that for every point (x_{1}, x_{2}, x_{3}) ∈ O we have x_{i}x_{j} ≥ 0. Renumbering the coordinate axes and replacing A with −A, if necessary, we can ensure that i = 1, j = 2, and x_{1}, x_{2} ≥ 0 for any (x_{1}, x_{2}, x_{3}) ∈ O. (Notice, that the assumption 0 ∈ A is not affected by these manipulations; on the other hand, the assumption that all points of A have non-negative third coordinate may not be valid any longer.)

Set B := A ∩ O, so that |B| ≥ |A|/4. Since 0 ∈ B and every point of B has non-negative first two coordinates, using Lemma 1 we get

|(B − B)^{+}| ≥ |(B_{3} − B_{3})^{+}| ≥ |B_{3}^{+}| = |B_{3}|.  (2)

Furthermore, by Lemma 1 and Theorem 1

|(B − B)^{+}| ≥ |(B_{1} − B_{1})^{+}| ≥ (|B_{1}|/2)^{2/3}  (3)

and similalry,

|(B − B)^{+}| ≥ (|B_{2}|/2)^{2/3}.  (4)

Finally, by Lemma 2

|(B − B)^{+}| ≥ \frac{1}{27} \frac{|B|^{3}}{|B_{1}||B_{2}||B_{3}|}.  (5)

From (2)–(5) we obtain

|(B − B)^{+}|^{5} ≥ \frac{|B|^{3}}{4 · 27} ≥ \frac{|A|^{3}}{4^{4} · 27}

whence

|(A − A)^{+}| ≥ |(B − B)^{+}| ≥ \frac{|A|^{3/5}}{(6912)^{1/5}} ≥ \frac{1}{6} |A|^{3/5}.

4. 4-dimensional sets: proof of Theorem 3

We need the following general result on hypergraphs.

Lemma 3. Let k ≥ 2 be an integer and suppose that G = (V, E) is a hypergraph, every edge of which is incident to at most k vertices. If G has at least two nonisolated vertices, then there exists an induced hypergraph G_{0} = (V_{0}, E_{0}) with |E_{0}| ≥ 0.9|E| and such that the minimal degree of G_{0} is at least γ|E|/(|V_{0}| log |V_{0}|), where γ = 1/(10 log k).

We present here an elegant proof, kindly communicated to us by Noga Alon.

Proof of Lemma 3. Dropping isolated vertices, we can assume that every vertex of G has degree at least 1. Let n := |V | and m := |E|. If m ≤ γ^{−1}n log n, then we can take G_{0} = G; assume that m > γ^{−1}n log n.

If G has a vertex of degree smaller than γm/(n log n), drop it, passing to an induced subgraph on n − 1 vertices; if this subgraph has a vertex of degree smaller than γm/((n − 1) log(n − 1)), drop this vertex, passing to an induced subgraph on n − 2 vertices, etc. We claim that the process ends before we get to a subgraph on n_{0} := ⌊n^{1/k}⌋ vertices. For, if this is wrong, then the number of edges we omitted to get to the subgraph on n_{0} vertices is less than

γm (\frac{1}{n log n} + \frac{1}{(n − 1) log(n − 1)} + ⋯ + \frac{1}{(n_{0} + 1) log(n_{0} + 1)})

< γm ∫_{n_{0}+1}^{n} \frac{dt}{t log t} + \frac{γm}{(n_{0} + 1) log(n_{0} + 1)}

= γm log \frac{log n}{log(n_{0} + 1)} + \frac{m}{10(n_{0} + 1) log(n_{0} + 1) log k}

< \frac{m}{10} + \frac{m}{20(log 2)^{2}}

< 0.3m,

so that the number of remaining edges is larger than 0.7m > 7n log n log k. On the other hand, the number of remaining vertices is n_{0}, and hence the number of remaining edges is at most n_{0}^{k}, implying 7n log n log k < n_{0}^{k} ≤ n, which leads to a contradiction.

Our claim is therefore established, and it remains to notice that when the process of dropping the vertices stops, we are left with an induced subgraph whose minimal degree satisfies the required condition, and the computation above shows that the number of edges in this subgraph is larger than 0.9m. □

We note that the factor log |V_{0}| in the statement of Lemma 3 is indeed required. To see this, consider the graph G = (V, E) on the vertex set V = {v_{1}, v_{2}, …, v_{n}}, whose edges join all pairs of vertices (v_{i}, v_{j}) with ij ≤ n. It is easy to check that |E| is of the order of magnitude n log n. Assume that G_{0} = (V_{0}, E_{0}) is an induced subgraph of G with |E_{0}| = Ω(n log n) edges. Since the largest index of a vertex in G_{0} is at least |V_{0}|, the degree (even in G) of the vertex with the largest index is at most \frac{n}{|V_{0}|} = O(\frac{|E(G)|}{|V_{0}| log |V_{0}|}).

Proof of Theorem 3. Consider the 4-uniform hypergraph G whose vertices are lines in ℝ^{4}, parallel to the coordinate axes and passing through the points of A, and whose edges are quadruples of such lines which meet in a point of A. (Loosely speaking, the edges of G are the points of A.) Applying Lemma 3 we find a subset A′ ⊆ A with |A′| ≥ 0.9|A| such that every line, parallel to a coordinate axis and passing through a point of A′, actually contains Ω(\frac{|A′|}{(|A′_{1}|+|A′_{2}|+|A′_{3}|+|A′_{4}|) log |A′|}) points of A′.

To simplify the notation we replace A by A′ and we assume that |A_{i}| ≤ |A_{4}| for i ∈ [1, 3]; we can then summarize saying that every line, parallel to a coordinate axis and passing through a point of A, contains Ω(|A|/(|A_{4}| log |A|)) points of A.

PROJECTING DIFFERENCE SETS 7

Furthermore, shifting A appropriately we arrange it so that 0 ∈ A and all points of A have non-negative last coordinate.

For x ∈ ℝ^{n} by A(x) we denote the set of all those points from A lying on the line, parallel to L_{4} and passing through x; that is, A(x) is the set of those points of A, coinciding with x in the first three coordinates. In view of 0 ∈ A and since the last coordinates of all points from A(x) are pairwise distinct and non-negative, if A(x) is non-empty then

(A(x))^{+} ⊆ (A − A)^{+} and |(A(x))^{+}| = |A(x)| = Ω (\frac{|A|}{|A_{4}| log |A|}) .  (6)

Choose an octant O of P_{4} that contains at least |A_{4}|/8 points of A_{4}, and let B := A_{4} ∩ O. If O is either the positive or the negative octant of P_{4}, then in view of Lemma 1 and taking into account that 0 ∈ B we obtain

|(A − A)^{+}| ≥ |(A_{4} − A_{4})^{+}| ≥ |(B − B)^{+}| ≥ |B|.

Furthermore, by Lemma 2 we have

|(A − A)^{+}| ≥ \frac{1}{4^{4}} \frac{|A|^{4}}{|A_{1}||A_{2}||A_{3}||A_{4}|} = Ω (\frac{|A|^{4}}{|B|^{4}} ) .

Combining the two last estimates we get

|(A − A)^{+}| ≥ Ω (|A|^{4/5}) .

We now assume that O is neither the positive, nor the negative octant of P_{4}. For each i ∈ [1, 4] we write

P_{i}^{+} := {(x_{1}, …, x_{4}) ∈ ℝ^{4} : x_{i} ≥ 0} and P_{i}^{−} := {(x_{1}, …, x_{4}) ∈ ℝ^{4} : x_{i} ≤ 0}.

Renumbering the coordinate axes, we can assume that either O = P_{1}^{−} ∩P_{2}^{−} ∩P_{3}^{+} ∩P_{4}, or O = P_{1}^{+} ∩ P_{2}^{+} ∩ P_{3}^{−} ∩ P_{4} holds, and we now consider these two cases separately.

Case 1. Suppose first that O = P_{1}^{+} ∩ P_{2}^{+} ∩ P_{3}^{−} ∩ P_{4}. In keeping with our standard notation, by B_{1}, B_{2}, and B_{3} we denote the orthogonal projections of B onto the hyperplanes P_{1}, P_{2}, and P_{3}, respectively.

By Lemmas 2 and 1 we have

|(A − A)^{+}| = Ω (\frac{|A|^{4}}{|B|^{4}} )  (7)

and

|(A − A)^{+}| ≥ |(B − B)^{+}| = Ω (\frac{|B|^{3}}{|B_{1}||B_{2}||B_{3}|}) .  (8)

8 RON HOLZMAN, VSEVOLOD F. LEV, AND ROM PINCHASI

By Lemma 1 and Theorem 2 we have

|(A − A)^{+}| ≥ |(B − B)^{+}| ≥ |(B_{1} − B_{1})^{+}| = Ω (|B_{1}|^{2/3}) ,  (9)

and similarly,

|(A − A)^{+}| = Ω (|B_{2}|^{2/3}) .  (10)

We notice next that for any b ∈ B the first and second coordinates of any point from (A(b))^{+} are equal to those of b, and hence if b′ ∈ B and b′′ ∈ B have different projections onto P_{3} ∩ P_{4}, then the sets (A(b′))^{+} and (A(b′′))^{+} are disjoint. Therefore, in view of (6) we get

|(A − A)^{+}| = Ω (|B_{3}|\frac{|A|}{|B| log |A|}) .  (11)

Raising (7)–(11) to the powers 1, 2, 3, 3, and 2, respectively, and multiplying out we obtain

|(A − A)^{+}|^{11} = Ω (|A|^{6}/(log |A|)^{2}) .  (12)

Case 2. Suppose now that O = P_{1}^{−} ∩ P_{2}^{−} ∩ P_{3}^{+} ∩ P_{4}. For i ∈ [1, 3] let l_{i} denote the number of points of the orthogonal projection of B onto L_{i}. By Lemmas 1 and 2 we have

|(A − A)^{+}| = Ω (\frac{|A|^{4}}{|B|^{4}} ) ,  (13)
|(A − A)^{+}| ≥ |(B − B)^{+}| = Ω (\frac{|B|^{3}}{|B_{1}||B_{2}||B_{3}|}) ,  (14)
|(A − A)^{+}| ≥ |(B_{1} − B_{1})^{+}| = Ω (\frac{|B_{1}|^{2}}{l_{2}l_{3}} ) ,  (15)

and similalry,

|(A − A)^{+}| = Ω (\frac{|B_{2}|^{2}}{l_{1}l_{3}} ) .  (16)

Evidently, we also have

|(A − A)^{+}| ≥ l_{1}  (17)

and

|(A − A)^{+}| ≥ l_{2},  (18)

and since B_{3} is contained in the negative quadrant of P_{3} ∩ P_{4}, in view of 0 ∈ B_{3} we have

|(A − A)^{+}| ≥ |(B_{3} − B_{3})^{+}| ≥ |B_{3}|.  (19)

Furthermore, notice that for any b ∈ B the third coordinate of any point from (A(b))^{+} is equal to that of b, and hence if b′ ∈ B and b′′ ∈ B differ in the third coordinate, then the sets (A(b′))^{+} and (A(b′′))^{+} are disjoint. Thus, it follows from (6) that

|(A − A)^{+}| ≥ Ω (l_{3} \frac{|A|}{|B| log |A|}) .  (20)

Squaring (14), (19), and (20) and multiplying out the resulting estimates, (13), and (15)–(18), we get (12). □

Acknowledgement

We are grateful to Noga Alon for communicating to us the present proof of Lemma 3.

References

[BS96] R. Balasubramanian and K. Soundararajan, On a conjecture of R.L. Graham, Acta Arith. 75 (1) (1996), 1–38.

[GR99] A. Granville and F. Roesler, The set of differences of a given set, Amer. Math. Monthly 106 (4) (1999), 338–344.

[MS69] J. Marica and J. Schönheim, Differences of sets and a problem of Graham, Canad. Math. Bull. 12 (1969), 635–637.

  E-mail address: holzman@techunix.technion.ac.il

Department of Mathematics, Technion - Israel Institute of Technology, Haifa 32000, Israel

  E-mail address: seva@math.haifa.ac.il

Department of Mathematics, The University of Haifa at Oranim, Tivon 36006, Israel

  E-mail address: room@math.technion.ac.il

Department of Mathematics, Technion - Israel Institute of Technology, Haifa 32000, Israel