Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Let A,W,s,kA,W,s,k satisfy the claim, and put n=∣W∣≥1n=|W|\ge1. For integers t,jt,j define

r(t)=∣{(a,a′)∈A2:a′−a=t}∣,rW(t)=∣{(w,w′)∈W2:w′−w=t}∣,F(j)=∣A∩(j+W)∣.r(t)=|\{(a,a')\in A^2:a'-a=t\}|,\qquad r_W(t)=|\{(w,w')\in W^2:w'-w=t\}|,\qquad F(j)=|A\cap(j+W)|.

All functions have finite support. Write ∥⋅∥2\|\cdot\|_2 and ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle for the norm and inner product in ℓ2(Z)\ell^2(\mathbb Z). An ordered pair (a,a′)(a,a') belongs to (j+W)×(j+h+W)(j+W)\times(j+h+W) for exactly rW(a′−a−h)r_W(a'-a-h) values of jj. Therefore

⟨F,F(⋅+h)⟩=∑tr(h+t)rW(t).(1)\langle F,F(\cdot+h)\rangle =\sum_t r(h+t)r_W(t). \tag{1}

At h=0h=0, the term t=0t=0 is knkn and all other representation counts are at most one. Since ∑trW(t)=n2\sum_t r_W(t)=n^2 and rW(0)=nr_W(0)=n,

∥F∥22≤kn+n2−n.(2)\|F\|_2^2\le kn+n^2-n. \tag{2}

For every t∈W−Wt\in W-W, the hypothesis ∣s∣>diam⁡W|s|>\operatorname{diam}W gives s+t≠0s+t\ne0. Its inclusion in A−AA-A and uniqueness give r(s+t)=1r(s+t)=1. Equation (1) at h=sh=s consequently gives

⟨F,F(⋅+s)⟩=n2.(3)\langle F,F(\cdot+s)\rangle=n^2. \tag{3}

Cauchy--Schwarz and translation invariance of the norm imply ∥F∥22≥n2\|F\|_2^2\ge n^2. Combining (2) and (3) gives

∥F−F(⋅+s)∥22=2∥F∥22−2n2≤2n(k−1).(4)\|F-F(\cdot+s)\|_2^2 =2\|F\|_2^2-2n^2\le2n(k-1). \tag{4}

Fix an integer K≥1K\ge1 and set g=K−1∑i=0K−1F(⋅+is)g=K^{-1}\sum_{i=0}^{K-1}F(\cdot+is). Telescoping (4), followed by the triangle inequality, gives

∥F−g∥2≤1K∑i=0K−1i2n(k−1)=K−122n(k−1).(5)\|F-g\|_2 \le\frac1K\sum_{i=0}^{K-1}i\sqrt{2n(k-1)} =\frac{K-1}{2}\sqrt{2n(k-1)}. \tag{5}

For distinct i,i′∈{0,…,K−1}i,i'\in\{0,\ldots,K-1\} we have ∣(i′−i)s∣>diam⁡W|(i'-i)s|>\operatorname{diam}W, so (i′−i)s∉W−W(i'-i)s\notin W-W. Thus the windows j+is+Wj+is+W are pairwise disjoint for each fixed jj. It follows that ∑iF(j+is)≤k\sum_i F(j+is)\le k, hence 0≤g(j)≤k/K0\le g(j)\le k/K. Each element of AA is counted in exactly nn windows j+Wj+W, so ∑jg(j)=∑jF(j)=kn\sum_j g(j)=\sum_j F(j)=kn. Therefore

∥g∥22≤kK∑jg(j)=k2nK.(6)\|g\|_2^2\le\frac{k}{K}\sum_jg(j)=\frac{k^2n}{K}. \tag{6}

Using (3), (5), (6), and the triangle inequality,

n≤∥F∥2≤∥g∥2+∥F−g∥2≤knK+K−122n(k−1).n\le\|F\|_2\le\|g\|_2+\|F-g\|_2 \le k\sqrt{\frac nK}+\frac{K-1}{2}\sqrt{2n(k-1)}.

Division by n\sqrt n proves the inequality for every K≥1K\ge1, including K=1K=1. Take K=⌈k1/3⌉K=\lceil k^{1/3}\rceil. Since K≥k1/3K\ge k^{1/3}, K−1≤k1/3K-1\le k^{1/3} and k−1≤kk-1\le k, its right-hand side is at most (1+1/2)k5/6(1+1/\sqrt2)k^{5/6}. Squaring proves

∣W∣≤(3/2+2)k5/3.□|W|\le(3/2+\sqrt2)k^{5/3}.\qquad\square

Restricted uniqueness. The proof only uses r(t)≤1r(t)\le1 for t∈(W−W)∖{0}t\in(W-W)\setminus\{0\} and r(s+t)=1r(s+t)=1 for t∈W−Wt\in W-W. If a set of kk integers represents every positive difference up to L≥1L\ge1 exactly once, put u=⌊(L+1)/2⌋u=\lfloor(L+1)/2\rfloor, W={0,…,u−1}W=\{0,\ldots,u-1\} and s=us=u. The restricted conditions hold because s+(W−W)={1,…,2u−1}s+(W-W)=\{1,\ldots,2u-1\} and 2u−1≤L≤2u2u-1\le L\le2u. Hence L≤(3+22)k5/3L\le(3+2\sqrt2)k^{5/3}. This recovers the leading term of L239 under its weaker hypothesis, without using that claim as an input or imposing uniqueness on differences larger than LL.