we-solve (beta)

Math-658-A4 · revision r1 · on Math-658

gpt pro 5.2 attempt on Math-658, version 2

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem #51 --- Round 2
  2. 1) ROUND-2 OBJECTIVE
  3. 2) ROUND-1 FOUNDATION USED
  4. 3) NEW INSIGHT / TOOL (ROUND-2)
  5. 4) ATTACK PLAN (ROUND-2)
  6. 5) WORK (ROUND-2)
  7. 5.1. A basic but powerful inequality: $\varphi(n)\ge \sqrt n$ except $n=2,6$
  8. 5.2. An explicit analytic upper bound on $n_a/a$
  9. 5.3. Extended computation up to $n\le 10^8$
  10. Method.
  11. Result (record up to $10^8$).
  12. Top record-holders (up to $10^8$).
  13. 6) ADVERSARIAL VERIFICATION
  14. 7) FINAL
  15. 8) COMPLETION ESTIMATE (MANDATORY)
  16. 9) REFERENCES

Erdős Problem #51 --- Round 2

1) ROUND-2 OBJECTIVE

Path (C): obstruction/bounding approach. Round 1 identified that large values of $n_a/a$ require $n_a$ to have many small prime divisors (Lemma 1 there), but left open whether this can be forced for the minimal preimage. The most promising next step is therefore to (i) obtain unconditional global upper bounds on $n_a/a$ (ruling out any "fast" divergence), and (ii) push computation far enough to see whether record values of $n_a/a$ grow at all.

2) ROUND-1 FOUNDATION USED

We rely on the following Round 1 items (without reproving them):
  • (R1--Lemma 1) $\displaystyle \frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}$.
  • (R1--Lemma 2) If $a=p-1$ with $p$ prime then $n_a=p$ and $n_a/a\to 1$ along this infinite family.
  • (R1--Lemma 3) For any totient value $a$, $n_a\ge a+1$.
  • (R1--Computation) For $a\le 20000$ the maximum observed ratio was $\approx 2.035$.

3) NEW INSIGHT / TOOL (ROUND-2)

  • New structural lemma: $\varphi(n)\ge \sqrt n$ for all $n\neq 2,6$. This implies quadratic compression for inverse totients: if $\varphi(n)=a$ and $a\ge 3$ then $n\le a^2$, hence $n_a\le a^2$.
  • New explicit analytic bound: using Rosser--Schoenfeld's inequality \[\frac{n}{\varphi(n)}<e^{\gamma}\log\log n+\frac{2.50637}{\log\log n}\qquad(n\ge 3),\] we obtain an explicit upper bound on $n_a/a$ in terms of $a$ alone.
  • Much larger computation: a totient sieve up to $n\le 10^8$ to locate record values of $n_a/a$.

4) ATTACK PLAN (ROUND-2)

  1. Close a Round 1 gap by proving a nontrivial unconditional upper bound for $n_a/a$.
  2. Extend the computational search from $n\le 3\cdot 10^5$ (Round 1) to $n\le 10^8$, recording the maximum of $n_a/a$ among all totients realized with minimal preimage $\le 10^8$.
  3. Try to identify rigid structural patterns among record-holders as a guide for (future) proofs or counterexamples.

5) WORK (ROUND-2)

5.1. A basic but powerful inequality: $\varphi(n)\ge \sqrt n$ except $n=2,6$

Lemma ( $\varphi(n)\ge \sqrt n$ for $n\neq 2,6$ ): For every integer $n\ge 1$ with $n\neq 2,6$, we have $\varphi(n)\ge \sqrt n$. Equivalently, $\varphi(n)^2\ge n$ for all $n\neq 2,6$.
Proof: Define \[g(n):=\frac{\varphi(n)^2}{n}. \] Since $\varphi$ is multiplicative and $n\mapsto 1/n$ is multiplicative, $g$ is multiplicative: if $(m,n)=1$ then \[ g(mn)=\frac{\varphi(mn)^2}{mn}=\frac{\varphi(m)^2}{m}\cdot\frac{\varphi(n)^2}{n}=g(m)g(n). \] Hence it suffices to analyze prime powers. For $p$ prime and $k\ge 1$, \[ g(p^k)=\frac{\varphi(p^k)^2}{p^k}=\frac{\left(p^{k-1}(p-1)\right)^2}{p^k}=p^{k-2}(p-1)^2. \] Odd primes. If $p\ge 3$ then for all $k\ge 1$, \[ g(p^k)\ge g(p)=\frac{(p-1)^2}{p} > 1, \] since $(p-1)^2-p=p^2-3p+1\ge 1$ for $p\ge 3$. So $g(p^k)>1$ for every odd prime power.

The prime $2$. We have $g(2)=\frac{1}{2}<1$, while for $k\ge 2$, \[ g(2^k)=2^{k-2}\ge 1. \] Now write $n=2^k m$ with $m$ odd. If $k\ge 2$ then $g(n)=g(2^k)g(m)\ge 1\cdot 1=1$. If $k=0$ then $n$ is odd and $g(n)=g(m)\ge 1$ (with equality only at $m=1$). If $k=1$ then $g(n)=g(2)g(m)=\tfrac12 g(m)$. This is $<1$ only if $g(m)<2$. But for odd $m>1$, the smallest possible value of $g(m)$ occurs at $m=3$, giving $g(3)=4/3<2$; for $m\ge 5$, one checks $g(m)\ge g(5)=16/5>2$ because every prime-power factor contributes $g(p^k)>1$ and the least such factor for odd primes is $g(5)=16/5$. Hence $g(2m)<1$ occurs exactly for $m=1$ (i.e. $n=2$) and $m=3$ (i.e. $n=6$).

Therefore $g(n)\ge 1$ for all $n\neq 2,6$, i.e. $\varphi(n)^2\ge n$ and $\varphi(n)\ge \sqrt n$ for $n\neq 2,6$. ∎

Corollary (Quadratic bound for inverse totients): If $a\ge 3$ is a totient value and $n$ is any solution of $\varphi(n)=a$, then $n\le a^2$. In particular, $n_a\le a^2$ for all totient values $a\ge 3$.
Proof: Let $\varphi(n)=a$ with $a\ge 3$. Then $n\neq 2,6$ (since $\varphi(2)=1$ and $\varphi(6)=2$), so by the lemma $n\le \varphi(n)^2=a^2$. Taking the minimum over solutions gives $n_a\le a^2$. ∎

5.2. An explicit analytic upper bound on $n_a/a$

We use the following explicit inequality of Rosser--Schoenfeld.
Theorem (Rosser--Schoenfeld $1962$, explicit upper bound): For every integer $n\ge 3$, \[ \frac{n}{\varphi(n)}<e^{\gamma}\log\log n+\frac{2.50637}{\log\log n}. \]
Theorem (Explicit upper bound for $n_a/a$): Let $a\ge 3$ be a totient value and $n_a:=\min\{n:\varphi(n)=a\}$. Then \[ \frac{n_a}{a}<e^{\gamma}\log\log(a^2)+\frac{2.50637}{\log\log(a^2)} \;=\; e^{\gamma}\left(\log\log a+\log 2\right)+\frac{2.50637}{\log\log a+\log 2}. \] In particular, $\frac{n_a}{a}=O(\log\log a)$.
Proof: Since $a\ge 3$, we have $n_a\ge a+1\ge 4$, hence $n_a\ge 3$. Applying Rosser--Schoenfeld to $n=n_a$ gives \[ \frac{n_a}{a}=\frac{n_a}{\varphi(n_a)}<e^{\gamma}\log\log n_a+\frac{2.50637}{\log\log n_a}. \] By the previous corollary, $n_a\le a^2$. As $\log\log$ is increasing on $[3,\infty)$, we have $\log\log n_a\le \log\log(a^2)$. Substituting yields the displayed bound. The $O(\log\log a)$ conclusion follows immediately. ∎

5.3. Extended computation up to $n\le 10^8$

Method.
We computed $\varphi(n)$ for all $1\le n\le 10^8$ by a standard totient sieve. For each totient value $a\le 10^8$ encountered, we recorded the least $n$ with $\varphi(n)=a$. Finally we scanned over all such $a$ to find the maximum of $n_a/a$.
Result (record up to $10^8$).
Among all totients $a$ with minimal preimage $n_a\le 10^8$, the maximum observed ratio was \[ \max \frac{n_a}{a} \approx 2.041378860109, \] attained at \[ a=2037248,\qquad n_a=4158795=3\cdot 5\cdot 17\cdot 47\cdot 347. \] For this record value, \[ \frac{n_a}{a}=\frac{4158795}{2037248}=\prod_{p\mid n_a}\frac{p}{p-1} =\frac32\cdot\frac54\cdot\frac{17}{16}\cdot\frac{47}{46}\cdot\frac{347}{346}. \]
Top record-holders (up to $10^8$).
The next-largest ratios observed are listed below. Empirically, every entry has the form $n_a=3\cdot 5\cdot 17\cdot 47\cdot q$ with $q$ prime, and hence $a=\varphi(n_a)=2\cdot 4\cdot 16\cdot 46\cdot (q-1)=5888\,(q-1)$.
rank$a$$n_a$$n_a/a$
1203724841587952.0413788601
26983168142261952.0372121937
38043008163834952.0369860381
48749568178216952.0368657058
511929088242935952.0365006109
612423680253003352.0364606139
714578688296868452.0363180144
823587328480238952.0360040357
925212416513317552.0359712849
1026236928534171452.0359527228

6) ADVERSARIAL VERIFICATION

  • Lemma $\varphi(n)\ge \sqrt n$ (except $2,6$). We reduced to prime powers via the multiplicativity of $g(n)=\varphi(n)^2/n$. All prime-power factors satisfy $g(p^k)>1$ except $g(2)=1/2$. The only way for a product of such factors to fall below $1$ is to include $g(2)$ and multiply it by an odd factor $g(m)<2$; checking odd $m$ shows only $m=1,3$ work, yielding $n=2,6$. Boundary checks: $\varphi(2)=1<\sqrt2$ and $\varphi(6)=2<\sqrt6$ do fail, as required.
  • Rosser--Schoenfeld bound usage. We only apply it for $n=n_a\ge 4$, so $\log\log n_a>0$. The step $\log\log n_a\le \log\log(a^2)$ uses the proven inequality $n_a\le a^2$.
  • Computation. The record value $n_a=3\cdot 5\cdot 17\cdot 47\cdot 347$ was independently verified by direct factorization and by checking $\varphi(n_a)=a$ via the product formula. The computation is still finite: it does not exclude larger ratios occurring at $n_a>10^8$.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED). We proved nontrivial global structure and bounds:
  • $\varphi(n)\ge \sqrt n$ for $n\neq 2,6$, implying $n_a\le a^2$ for every totient $a\ge 3$.
  • Using Rosser--Schoenfeld, we derived an explicit unconditional upper bound $\displaystyle \frac{n_a}{a}<e^{\gamma}\log\log(a^2)+\frac{2.50637}{\log\log(a^2)}$, hence $n_a/a=O(\log\log a)$.
  • Computation up to $n_a\le 10^8$ finds a stable maximum ratio $\approx 2.0413788601$ (no growth beyond the Round 1 range), with record-holders of a very rigid empirical shape.
The main Erdős question (existence of an infinite set with $n_a/a\to\infty$) remains open.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 40%

9) REFERENCES

  • J. B. Rosser and L. Schoenfeld, "Approximate formulas for some functions of prime numbers", Illinois J. Math. 6 $1962$, Theorem 15 (explicit bounds for $n/\varphi(n)$).
  • E. W. Weisstein, "Totient Function", MathWorld (states $\varphi(n)\ge \sqrt n$ for $n\neq 2,6$ and cites Kendall--Osborn $1965$ and Mitrinović--Sándor $1995$).