betaFeedback

WorksMathematics

A periodic-summand characterization for Erdős problem 335

Abstract

We characterize pairs of positive-density subsets of the positive integers for which the ordinary density of their sumset equals the sum of their densities. The modular boundary is controlled by literal residue supports. Above that boundary, the classification consists of parallel Bohr intervals with finite backgrounds, two periodic templates with a literal fringe test, or one sparse exceptional section with an exact terminal condition. This overview states the characterization and explains the proof structure. The linked development gives the detailed mathematical arguments and verifies the complete result in Lean using the original positive-integer counts.

Introduction

Throughout, AA and BB are subsets of the positive integers, and both ordinary densities exist and are positive. All sumsets use the actual elements of the sets. For a positive integer qq, let Rq(A)R_q(A) be the set of residues represented by AA. Put

d(A)=lim⁡N→∞∣A∩[1,N]∣N,s=d(A)+d(B),(1)d(A) = \lim_{N\to\infty} \frac{|A \cap[1,N]|}{N}, \qquad s = d(A) + d(B), \tag*{(1)}
Rq(A)={a mod q:a∈A},γ=inf⁡q≥1∣Rq(A)+Rq(B)∣q.(2)R_q(A) = \{a \bmod q : a \in A\}, \qquad\gamma= \inf_{q\ge1} \frac{|R_q(A) + R_q(B)|}{q}. \tag*{(2)}

Theorem 1.1 (Classification). The equality under study is

d(A+B)=d(A)+d(B).(3)d(A+B) = d(A) + d(B). \tag*{(3)}

Equality always holds at the modular boundary:

γ=s⟹d(A+B)=s.(4)\gamma= s \quad\Longrightarrow\quad d(A+B) = s. \tag*{(4)}

If γ<s\gamma< s, equality is impossible. When s<γs < \gamma, equality holds precisely when at least one of the three structural alternatives in § 2 holds. The alternatives retain the literal exceptional elements of AA and $B.

The three structural alternatives

Parallel Bohr intervals with finite backgrounds. Choose a modulus hh, the actual supports S=Rh(A)S = R_h(A) and T=Rh(B)T = R_h(B), and distinguished residues i∈Si \in S and j∈Tj \in T. Every background section is full up to density zero. The distinguished output residue has a unique expression in the quotient, and the support count satisfies

∣S+T∣=∣S∣+∣T∣−1,{(r,t)∈S×T:r+t=i+j}={(i,j)}.(5)|S+T| = |S| + |T| - 1,\qquad\{(r,t) \in S \times T : r+t=i+j\} = \{(i,j)\}. \tag*{(5)}

After rescaling the distinguished sections, each is a literal subset of a closed-arc pullback under the same irrational circle rotation. Each fills its pullback up to density zero. The two arc lengths are positive and have sum less than one. The modulus h=1h=1 is allowed.

Two periodic templates with literal fringes. Write Pq(S)P_q(S) for the positive integers whose residue modulo qq lies in SS. The notation ∼d\sim_d means that the symmetric difference has ordinary density zero. There are nonempty masks SS and TT such that

A∼dPq(S),B∼dPq(T).(6)A \sim_d P_q(S), \qquad B \sim_d P_q(T). \tag*{(6)}

The baseline formed from the actual supports and the two masks is

W=(Rq(A)+T)∪(S+Rq(B)),∣W∣=∣S∣+∣T∣.(7)W = (R_q(A) + T) \cup(S + R_q(B)), \qquad|W| = |S| + |T|. \tag*{(7)}

For every output residue outside WW, the sums of the literal fringes A∖Pq(S)A \setminus P_q(S) and B∖Pq(T)B \setminus P_q(T) satisfy the vanishing interval-packing test described in § 3. The masks can be proper subsets of the actual supports.

One sparse exceptional section. Use the same finite background frame and unique-expression condition as in the first alternative. One exceptional section UU is nonempty and has density zero. Its partner VV has density xx strictly between zero and one. The two roles may be exchanged. Normalize the sparse section at its least element:

u0=min⁡U,D={u−u0:u∈U}.(8)u_0 = \min U, \qquad D = \{u-u_0 : u \in U\}. \tag*{(8)}

If UU is a singleton, the terminal condition holds. Otherwise g=gcd⁡(D)>0g = \operatorname{gcd}(D) > 0 and V+g∼dVV + g \sim_d V. For finite UU this is the remaining terminal condition. For infinite UU, the literal sums of D/gD/g with each rescaled gg-residue section of VV must satisfy the escape-packing test outside that section.

The literal interval-packing test

The terminal tests operate on runs of consecutive block indices. They keep initial elements, singleton runs and sparse sections. A residue section and the carry in a sum are given by

Eq,r={k≥0:qk+r∈E},κ(r,t)=⌊r+tq⌋,0≤r,t<q.(9)E_{q,r} = \{k \ge0 : qk + r \in E\}, \qquad\kappa(r,t) = \left\lfloor\frac{r+t}{q} \right\rfloor, \qquad0 \le r,t < q. \tag*{(9)}

Take consecutive source runs [a,b][a,b] and [c,d][c,d]. The represented output indices fill the complete integer interval

[a,b]+[c,d]+κ=[a+c+κ,b+d+κ].(10)[a,b] + [c,d] + \kappa= [a+c+\kappa,b+d+\kappa]. \tag*{(10)}

Clip every interval to the first NN indices, including index zero. In the two-template alternative, collect the intervals in each output residue outside WW. In the sparse alternative, intersect them with complementary runs of the relevant section of VV. Only finitely many clipped intervals contribute.

Packing size. For a finite interval family INI_N, let P(IN)P(I_N) be the greatest total number of integer points in a pairwise disjoint subfamily. The required test is P(IN)=o(N)P(I_N) = o(N), separately in every relevant residue. The elementary comparison is

P(IN)≤∣⋃IN∣≤3P(IN).(11)P(I_N) \le\left|\bigcup I_N\right| \le3P(I_N). \tag*{(11)}

The comparison shows that the test is equivalent to zero density of the designated escaping indices. To prove the upper bound, select a longest remaining interval and remove every interval meeting it. Each removed interval lies in the selected interval enlarged by at most its length on each side. The selected intervals are disjoint, which gives the factor three.

Why literal data matter. A sparse modification of an input can create a whole new residue class in its sumset. The characterization therefore retains the actual supports and tests the exceptional sums. In the infinite sparse case, invariance under each fixed translate is supplemented by a test on the full union of escaping sums.

The numerical case. The parameter γ\gamma is the upper Buck density of A+BA+B. If γ=s\gamma= s and the lower ordinary density were smaller than ss, the integer Kneser theorem [2] would give an ultimately periodic output with ordinary density equal to its Buck density. This contradicts the supposed deficit and proves the boundary case.

Proof structure in the strict-gap case

Let b∗(E)b^*(E) denote the upper Buck density of EE, and set

Δ=γ−s,δA=b∗(A)−d(A),δB=b∗(B)−d(B).(12)\Delta= \gamma- s,\qquad\delta_A = b^*(A) - d(A),\qquad\delta_B = b^*(B) - d(B). \tag*{(12)}

Local structure and the choice of scales. A zero input gap yields a periodic-in-density summand through the compact inverse argument. When both input gaps exceed Δ\Delta, the matched local inverse arguments give the parallel-Bohr alternative. In the remaining case, bounded-index local inverse theory makes one actual input periodic in each limiting window.

The global step starts with joint Lipschitz limits of cumulative residue counts. A common subsequence and a countable diagonal construction provide Fourier models at every fixed ambient enlargement. The window scale dominates all approximation errors:

Hk→∞,Hk/Nk→0,error⁡k/Hk→0.(13)H_k \to\infty,\qquad H_k/N_k \to0,\qquad\operatorname{error}_k/H_k \to0. \tag*{(13)}

From local labels to one periodic summand. At almost every positive macroscopic time, derivatives of the cumulative limits give a finitely labeled profile. The labels record the periodic masks and saturation of the fixed-translate baselines. Literal translations between windows give the cross-time inequality

cr+t(x+y)≥max⁡{ar(x),bt(y)}if ar(x)>0, bt(y)>0.(14)c_{r+t}(x+y) \ge\max\{a_r(x),b_t(y)\}\quad\text{if }a_r(x)>0,\ b_t(y)>0. \tag*{(14)}

Two times with the same label have that label at their sum, almost everywhere. A bounded positive-measure piece of a label has a self-convolution positive on an interval. Repeated addition gives a tail. Disjoint labels therefore cannot both have positive measure, so a single label holds almost everywhere on the positive axis.

The normalized prefix-profile sequence has vanishing successive increments. Its cluster points lie in finitely many closed slices, and the label rules separate those slices. The sequence therefore selects one slice. One input coordinate converges to a fixed periodic mask, giving an ordinary periodic-in-density summand.

Exact reduction and sufficiency. Once one summand is periodic in density, use its mask and the other input’s actual residue support to form the fixed-translate baseline. If that baseline fills the output density, both inputs have periodic templates. If the baseline has smaller density, the reduction gives the finite background frame with one null section. Finite sparse sets use gcd-shift invariance and finite unions. Infinite sparse sets use the escape test to give d((D+V)∖V)=0d((D+V)\setminus V)=0. The Bohr alternative uses literal arc containment, equidistribution and the Kneser lower bound. Recombining the background and active sections proves the converse in every alternative.

The mathematical source package provides the reading order and the detailed supporting arguments. The classification proof links its local inverse arguments and exact reductions. The expanded gluing proof gives the common scale selection, comparison of windows and passage to one ordinary periodic summand.

Formal verification and provenance

The complete formal result is the closed theorem

Erdos335.Proposed.full_periodic_classification.

Its type is PeriodicRefinedSolution. The theorem

Erdos335.Proposed.full_periodic_classification_original_positive_counts

writes the same classification using the original counts on {1,…,N}\{1,\ldots,N\}.

CheckRecorded result
New supporting modules45 compiled
Exact declaration and axiom audit2,602 targets passed
Allowed proof axiomspropext, Classical.choice, Quot.sound
Fresh full-closure kernel replayPassed in 1,460.406 seconds
Project object files bound890
Source, object and runtime hashesUnchanged across replay

The runtime is Lean 4.34.0, with Mathlib revision 5ed2965256430c3649e86755f9576b54eca72435. The checked proof commit is 63e4377a3f62cdf4a989b2559d8f9c7341c78789. The checker ran leanchecker --fresh -v Challenge. The verification record includes the proof revisions, logs and reproduction instructions. The original overview accompanies Justin Sun Prize submission JSP-000278.

The prize submission credits OpenAI Codex assistance in the Lean formalization. The original overview reports that its literature search found no earlier matching full characterization in the public record it checked. Publication priority and Justin Sun Prize acceptance are submitted for independent review.

References

References

  1. [2]M. Kneser, Abschätzung der asymptotischen Dichte von Summenmengen, Mathematische Zeitschrift 58 (1953), 459–484.DOI

Paper details

vlnc:W_twqwta3e
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents