Reused writeup on Math-949 (gpt pro 5.2)

Erdős Problem 821 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/821

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/821.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/821.tex.

FORMAL RESTATEMENT

Let $\varphi$ denote Euler's totient function. For each integer $n\ge 1$, define \[ g(n) := \left|\{m\in\mathbb{Z}_{\ge 1} : \varphi(m)=n\}\right|. \] The question is:

Conjecture. For every $\varepsilon>0$, there exist infinitely many integers $n\ge 1$ such that \[ g(n) > n^{1-\varepsilon}. \]

Conventions/edge cases.

• $\mathbb{Z}_{\ge 1}=\{1,2,3,\dots\}$.
• The inequality $g(n) > n^{1-\varepsilon}$ is meaningful for all $n\ge 1$ (for $n=1$, it reads $g(1)>1^{1-\varepsilon}=1$).

QUICK LITERATURE/CONTEXT CHECK

From the problem statement: Pillai proved $\limsup g(n)=\infty$, Erdős proved $g(n)>n^c$ for infinitely many $n$ for some $c>0$, and Lichtman obtained infinitely many $n$ with $g(n)>n^{0.71568\cdots}$ by finding many primes $p$ whose $p-1$ has no large prime factor (improving earlier exponents, e.g. Baker--Harman). The statement also notes an implication from a conjecture about shifted primes $p-1$ being $p^{\varepsilon}$-smooth.

In what follows I do not use any result beyond what is explicitly written above; instead I prove a few unconditional, elementary lemmas and record computational sanity checks.

ATTACK PLAN

• Proof track (ambitious): Try to build many distinct $m$ with the same totient value $n$ by multiplicative constructions. The main obstruction is that keeping $\varphi(m)$ fixed while varying $m$ typically requires deep information about primes $p$ with prescribed smoothness of $p-1$.
• Disproof track: Attempt to show the conjecture fails by proving a universal upper bound $g(n) \le n^{1-\varepsilon_0}$ for some fixed $\varepsilon_0>0$. This contradicts known results quoted in the problem statement (e.g. $\limsup g(n)=\infty$), so a disproof seems implausible.
• What I will do here: Provide rigorous small-case computations and two+ problem-specific lemmas that clarify the structure of $g(n)$ (parity/vanishing on odd $n$, and explicit infinite families with $g(n)\ge 2$).

WORK

FAST REALITY CHECK (exact computation for small $n$).

I computed $g(n)$ exactly for all $1\le n\le 200$ by enumerating $m$ with $\varphi(m)\le 200$ (the maximum $m$ occurring in this range was $840$). The values in this range satisfy:

• $g(1)=2$ (solutions $m=1,2$).
• $g(n)=0$ for every odd $n>1$.
• The largest values up to $200$ are $g(144)=21$ and $g(192)=21$; also $g(72)=17$, $g(96)=17$, $g(120)=17$.

These are only sanity checks; they do not address the conjectured exponent $1-\varepsilon$.

Lemma (Totients are even beyond $2$). For every integer $m>2$, $\varphi(m)$ is even. Consequently, \[ g(n)=0\quad\text{for every odd }n>1,\qquad\text{and}\qquad g(1)=2. \]

Proof. Let $m>2$. Consider the multiplicative group of units $(\mathbb{Z}/m\mathbb{Z})^\times$, which has size $\varphi(m)$. The element $-1\in(\mathbb{Z}/m\mathbb{Z})^\times$ because $\gcd(-1,m)=1$. Also $-1\not\equiv 1\pmod m$ since $m>2$.

Define the map $f:(\mathbb{Z}/m\mathbb{Z})^\times\to(\mathbb{Z}/m\mathbb{Z})^\times$ by $f(x)\equiv -x\pmod m$. This map is an involution with no fixed points: if $f(x)=x$ then $2x\equiv 0\pmod m$. Since $x$ is a unit, this implies $m\mid 2$, hence $m\le 2$, contradicting $m>2$.

Thus $(\mathbb{Z}/m\mathbb{Z})^\times$ decomposes into disjoint 2-cycles under $f$, so its cardinality $\varphi(m)$ is even.

Now if $n$ is odd and $n>1$, there is no $m>2$ with $\varphi(m)=n$, and the only remaining possibilities are $m\in\{1,2\}$ which both satisfy $\varphi(m)=1$. Hence $g(1)=2$ and $g(n)=0$ for odd $n>1$. $\square$

Lemma (An infinite family with $g(n)\ge 2$). For every odd prime $p$, one has \[ g(p-1)\ge 2. \] More precisely, $\varphi(p)=\varphi(2p)=p-1$.

Proof. Let $p$ be an odd prime. Then $\varphi(p)=p-1$.

Since $\gcd(2,p)=1$ and $\varphi$ is multiplicative on coprime inputs, we have \[ \varphi(2p)=\varphi(2)\varphi(p)=1\cdot (p-1)=p-1. \] The integers $p$ and $2p$ are distinct, so they contribute at least two distinct solutions to $\varphi(m)=p-1$, giving $g(p-1)\ge 2$. $\square$

Lemma (One explicit construction of a preimage). Let $k\ge 0$ and let $p_1,\dots,p_r$ be distinct odd primes. Define \[ m := 2^{k+1}\prod_{i=1}^r p_i,\qquad n := 2^k\prod_{i=1}^r (p_i-1). \] Then $\varphi(m)=n$, so $g(n)\ge 1$.

Proof. Because the factors $2^{k+1}$ and $\prod p_i$ are coprime, multiplicativity gives \[ \varphi(m)=\varphi(2^{k+1})\,\varphi\left(\prod_{i=1}^r p_i\right). \] We have $\varphi(2^{k+1})=2^k$. Also, since the $p_i$ are distinct primes, \[ \varphi\left(\prod_{i=1}^r p_i\right)=\prod_{i=1}^r \varphi(p_i)=\prod_{i=1}^r (p_i-1). \] Multiplying yields $\varphi(m)=2^k\prod_{i=1}^r (p_i-1)=n$. $\square$

VERIFICATION

• Lemma (Totients are even beyond $2$): The involution $x\mapsto -x$ on units has no fixed points exactly because $m>2$; for $m=1,2$ the argument fails and indeed $\varphi(1)=\varphi(2)=1$ is odd.
• Lemma (An infinite family with $g(n)\ge 2$): Requires $p$ odd so that $p$ and $2p$ are distinct and $\varphi(2)=1$ applies; for $p=2$, $p-1=1$ and $g(1)=2$ still, but the displayed equalities change.
• Lemma (One explicit construction of a preimage): Checked multiplicativity hypotheses: $\gcd(2^{k+1},\prod p_i)=1$ since all $p_i$ are odd.
• Computation: the brute-force range $m\le 200000$ found all solutions with $\varphi(m)\le 200$ and the maximum $m$ observed was $840$, so the $g(n)$ values for $n\le 200$ are exact.

FINAL

UNRESOLVED.

1. (i) Strongest proved partial result. Elementary structure results: $g(1)=2$ and $g(n)=0$ for odd $n>1$; also $g(p-1)\ge 2$ for every odd prime $p$ (so $g(n)\ge 2$ for infinitely many $n$).
2. (ii) First gap. Prove, for arbitrary fixed $\varepsilon>0$, that there exist infinitely many $n$ admitting at least $n^{1-\varepsilon}$ distinct solutions to $\varphi(m)=n$.
3. (iii) Top 3 next moves.
   1. Prove (or computationally test in growing ranges) a quantitative lower bound on the number of primes $p\le x$ for which $p-1$ is $x^{\theta}$-smooth, with $\theta$ as small as possible; then translate such a bound into a lower bound for $g(n)$ via the standard "smooth $p-1$" construction sketched in the problem statement.
   2. Systematically search for explicit families of $n$ with many representations of the form $n=\varphi(m)$ using multiplicativity: enforce many independent "choices" of prime powers in $m$ while keeping $\varphi(m)$ fixed.
   3. Compute $\max_{n\le N} g(n)$ and candidate extremizers for larger $N$ (e.g. $10^6,10^7$) to guess the right structure of large fibers and to test whether $g(n)$ behaves like a large power of $n$ along any explicit family.
4. (iv) Minimal counterexample structure (if the conjecture were false). One would need an $\varepsilon_0>0$ and an $N_0$ such that for all $n\ge N_0$, $g(n)\le n^{1-\varepsilon_0}$. Such a failure would have to persist even on $n$ built from many smooth shifted primes $p-1$; in particular it would likely force a strong scarcity of primes with very smooth $p-1$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.