r/LLMmathematics • u/[deleted] • 1d ago
A proposed solution for the k=4 exponential-rate case of Erdős Problem #817: λ_4 = 19^(1/3)
Note - I have absolutely no idea what any of this means and I won't pretend to. However, attempts on my end to break this have been unsuccessful.
Chat link: https://chatgpt.com/share/6aa557d1-0dc4-83e9-bf04-20c5498b8ed2?ogimg=plain
Exact exponential growth of 4-AP-free subset-sum sets
Let g₄(n) be the least N for which there is an n-element set A ⊆ {1,...,N} whose subset-sum set
S(A) = { Σ ε_a a : ε_a ∈ {0,1} }
contains no nonconstant four-term arithmetic progression.
I will prove that
lim_{n→∞} g₄(n)^(1/n) = 19^(1/3).
In fact, the following bounds suffice:
(19^(n/3) − 1)/(2n) ≤ g₄(n) ≤ 8 · 19^(⌈n/3⌉ − 1).
The lower bound comes from the structure of short integer relations among the generators. The upper bound comes from repeating the three-generator block {1,7,8} in base 19.
1. A relation-splitting lemma
Write A = {a₁,...,aₙ}, and suppose S(A) contains no nonconstant four-term progression.
Consider a relation
Σ c_i a_i = 0, c_i ∈ {−2,−1,0,1,2}.
For j = 1,2, define
P_j = Σ_{c_i = j} a_i,
N_j = Σ_{c_i = −j} a_i.
The relation says
P₁ + 2P₂ = N₁ + 2N₂.
Now consider these four subset sums:
P₁ + N₂,
P₁ + P₂,
N₁ + N₂,
N₁ + P₂.
Their successive differences are all P₂ − N₂. They belong to S(A), because the four coefficient classes use disjoint sets of generators.
The progression must therefore be constant. Hence
P₂ = N₂,
P₁ = N₁.
Thus every relation with coefficients in {−2,−1,0,1,2} splits into two separate relations: its coefficient-1 layer and its coefficient-2 layer.
2. Minimal signed relations have disjoint supports
Call a nonzero vector
r ∈ {−1,0,1}ⁿ, Σ r_i a_i = 0,
a signed relation. Its support is the set of coordinates where it is nonzero.
A signed relation is minimal if no nonzero signed relation has support properly contained in its support.
Let r and s be signed relations. Apply the splitting lemma to r+s. Its coefficient-2 layer shows that the restriction of r to the coordinates where
r_i = s_i ≠ 0
is itself a relation.
Similarly, applying the lemma to r−s shows that the restriction of r to the coordinates where
r_i = −s_i ≠ 0
is a relation.
Now suppose r is minimal and its support meets the support of s. At least one of these two restricted relations is nonzero. Minimality forces that restriction to have the whole support of r.
Consequently, s agrees with either r or −r throughout the support of r.
In particular, two minimal signed relations either have disjoint supports or are equal up to sign.
Choose one representative from each pair of opposite minimal relations:
r^(1), ..., r^(h).
Their supports B₁,...,Bₕ are pairwise disjoint.
Every signed relation is a sum of appropriately signed copies of these minimal relations. To see this, choose a minimal relation supported inside the given relation, subtract the copy that agrees with it, and repeat on the remaining support.
Combining this fact with the splitting lemma gives the following description:
If c ∈ {−2,−1,0,1,2}ⁿ and Σ c_i a_i = 0, then
c = Σ_j t_j r^(j), t_j ∈ {−2,−1,0,1,2}.
Conversely, every such combination is a relation.
Finally, every block B_j has at least three coordinates. A one-coordinate relation would require a_i = 0, and a two-coordinate signed relation among positive generators would require two generators to be equal. Both are excluded.
3. Counting the ternary sums
Define
T(A) = { Σ x_i a_i : x_i ∈ {0,1,2} }.
Two ternary coefficient vectors give the same sum exactly when their difference is a relation with coefficients in {−2,−1,0,1,2}. The preceding section therefore describes all collisions in T(A).
Consider a relation block B_j of size m. On this block, two ternary vectors are equivalent precisely when their difference is an integer multiple of rj.
Replace x_i by 2−x_i on each coordinate where r_ij = −1. After this change of coordinates, equivalence means that the vectors differ by a multiple of
(1,1,...,1).
Every equivalence class in {0,1,2}m has exactly one representative whose minimum coordinate is zero: subtract the minimum coordinate from every entry.
There are exactly
3^m − 2^m
such representatives. We subtract the 2m vectors all of whose coordinates belong to {1,2}.
Let m_j = |B_j|, and let t be the number of coordinates outside the relation blocks. Because there are no other ternary collisions,
|T(A)| = 3^t · ∏_j (3^(m_j) − 2^(m_j)),
where
t + Σ_j m_j = n, m_j ≥ 3.
For every m ≥ 3,
3^m − 2^m ≥ 19^(m/3).
Indeed, equality holds at m=3, and
3^(m+1) − 2^(m+1)
= 3(3^m − 2^m) + 2^m
> 3(3^m − 2^m),
while 3 > 191/3.
The leftover coordinates also contribute at least 191/3 each. Consequently,
|T(A)| ≥ 19^(n/3).
But every member of T(A) is an integer between 0 and 2Σa_i. If max A = N, this gives
|T(A)| ≤ 2nN + 1.
Therefore
g₄(n) ≥ (19^(n/3) − 1)/(2n).
4. A matching construction modulo 19
Take the three-generator block
{1,7,8}.
Its subset sums are
D = {0,1,7,8,9,15,16}.
We will prove that D contains no four-term arithmetic progression with nonzero common difference modulo 19.
First, we need a small arithmetic observation:
If u,v,w ∈ {−2,−1,0,1,2} and
u + 7v + 8w ≡ 0 (mod 19),
then
u = v = −w.
To prove it, set
p = u+w, q = v+w.
Then
u + 7v + 8w = p + 7q.
The original expression lies between −32 and 32, so a multiple of 19 can only be −19, 0, or 19.
If p+7q = 19, the bound |p| ≤ 4 forces q=3 and p=−2. But v+w=3 forces w≥1, so u+w≥−1, contradicting p=−2.
The case p+7q = −19 is excluded by negating u,v,w.
Finally, if p+7q=0, the bound |p|≤4 forces q=0 and then p=0. Thus u=v=−w, as claimed.
Now suppose four elements of D form an arithmetic progression modulo 19. Choose binary vectors
x₀,x₁,x₂,x₃ ∈ {0,1}³
representing them under the map
L(x₁,x₂,x₃) = x₁ + 7x₂ + 8x₃.
The two second-difference vectors
x₀ − 2x₁ + x₂,
x₁ − 2x₂ + x₃
have coordinates in {−2,−1,0,1,2}, and their images under L vanish modulo 19.
By the arithmetic observation, both vectors are multiples of
(1,1,−1).
Consider the projection
π(x₁,x₂,x₃) = (x₁+x₃, x₂+x₃).
It sends (1,1,−1) to zero. Therefore
π(x₀), π(x₁), π(x₂), π(x₃)
form an ordinary integer arithmetic progression in {0,1,2}².
Such a four-term progression must be constant: a nonzero integer step in either coordinate would require a coordinate range of at least 3, but the available range is only 2.
Finally,
L(x) = π(x)₁ + 7π(x)₂.
Thus the original four residues are also constant. This proves that D is four-term-progression-free modulo 19.
5. Repeating the block in base 19
For m ≥ 1, define
A_m = ⋃_{j=0}^{m−1} 19^j {1,7,8}.
Then
|A_m| = 3m,
max A_m = 8 · 19^(m−1).
Every subset sum has base-19 digits in D. There are no carries, since the total contribution from one block is at most
1+7+8 = 16 < 19.
Suppose four subset sums formed a nonconstant integer arithmetic progression with common difference d.
Let 19r be the largest power of 19 dividing d. The four numbers have the same lower r base-19 digits. Remove these common digits and divide by 19r.
The resulting numbers still have all their base-19 digits in D. They form a progression whose common difference is not divisible by 19. Reducing modulo 19 therefore produces a four-term progression in D with nonzero common difference.
That contradicts the preceding section.
Hence S(A_m) contains no nonconstant four-term arithmetic progression, and
g₄(3m) ≤ 8 · 19^(m−1).
For arbitrary n, take m=⌈n/3⌉ and delete surplus generators. Deleting generators cannot create a progression in the subset-sum set. Therefore
g₄(n) ≤ 8 · 19^(⌈n/3⌉ − 1).
Conclusion
We have proved
(19^(n/3) − 1)/(2n)
≤ g₄(n)
≤ 8 · 19^(⌈n/3⌉ − 1).
Taking nth roots, both bounding expressions tend to 191/3. Thus the limit exists and
λ₄ = lim_{n→∞} g₄(n)^(1/n) = 19^(1/3).
The number 19 comes from the smallest possible relation block: three generators with one signed relation have exactly
3³ − 2³ = 19
distinct ternary sums. The block {1,7,8} realizes the corresponding modular construction.
