we-solve (beta)

Math-658-A3 · revision r1 · on Math-658

gpt pro 5.2 attempt on Math-658

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
  2. FORMAL RESTATEMENT.
  3. QUICK LITERATURE/CONTEXT CHECK.
  4. ATTACK PLAN.
  5. WORK.
  6. FAST REALITY CHECK (numerics).
  7. Lemma 1 (basic ratio identity).
  8. Lemma 2 (prime-shifted totients have minimal preimage equal to the prime).
  9. Lemma 3 (a general lower bound).
  10. VERIFICATION.
  11. FINAL.

Erdős Problem #51

Problem statement (from the problem file). Is there an infinite set $A\subset\mathbb{N}$ such that for every $a\in A$ there is an integer $n$ with $\varphi(n)=a$, and yet if $n_a$ is the smallest such integer then $n_a/a\to\infty$ as $a\to\infty$?
FORMAL RESTATEMENT.
Does there exist an infinite set $\mathcal{A}\subset\mathbb{N}$ such that
  • for every $a\in\mathcal{A}$, the equation $\varphi(n)=a$ has at least one solution $n\in\mathbb{N}$;
  • writing $n_a:=\min\{n\in\mathbb{N}:\varphi(n)=a\}$, one has $\lim_{\substack{a\to\infty\\ a\in\mathcal{A}}} \frac{n_a}{a}=\infty$.
QUICK LITERATURE/CONTEXT CHECK.
The problem file mentions Carmichael's question about uniqueness of solutions to $\varphi(n)=t$ and that Erdős proved: if there exists such a $t$ with a unique preimage then there are infinitely many. I do not use any further results.
ATTACK PLAN.
Construction track: Search for a family of totients $a$ that force the smallest preimage to have many small prime factors, making $n_a/a$ large. Disproof track: Try to show that for every totient value $a$ there is always some preimage $n$ with $n\ll a(\log\log a)$ or similar, which would preclude divergence. Reality check: Compute $n_a$ for all $a$ realized by $\varphi(n)$ up to a cutoff and inspect ratios.
WORK.
FAST REALITY CHECK (numerics).
Scanning all $n\le 300000$ and recording, for each totient value $a=\varphi(n)\le 20000$, the minimal preimage $n_a$, we found:
  • among the $4486$ values $a\le 20000$ that occur as $\varphi(n)$ with some $n\le 300000$, the maximum observed ratio $n_a/a$ was about $2.035$ (attained at $a=5888$, $n_a=11985$).
  • for values of the form $a=p-1$ with $p$ prime, one has $n_a=p$ and $n_a/a=1+1/a$, quickly tending to $1$.
This finite search does not show large ratios, but it is far from the asymptotic regime.
Lemma 1 (basic ratio identity).
For every $n\ge 1$, \[ \frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{1}{1-1/p}. \]

Proof. This is immediate from Lemma 1 of Problem #50: $\varphi(n)/n=\prod_{p\mid n}(1-1/p)$, hence invert. $\square$

Lemma 2 (prime-shifted totients have minimal preimage equal to the prime).
If $p$ is prime and $a:=p-1$, then the smallest $n$ with $\varphi(n)=a$ is $n_a=p$.

Proof. We have $\varphi(p)=p-1=a$, so $n_a\le p$. On the other hand, for every integer $n>1$, one has $\varphi(n)\le n-1$ with equality only when $n$ is prime. Thus if $\varphi(n)=p-1$, then $n\ge p$. Combining gives $n_a=p$. $\square$

Lemma 3 (a general lower bound).
For any $a\ge 1$ that occurs as $a=\varphi(n)$ for some $n$, one has $n_a\ge a+1$.

Proof. If $a=1$ then $n_a=1$ and the claim holds. For $a\ge 2$, any $n$ with $\varphi(n)=a$ satisfies $n>1$ and hence $\varphi(n)\le n-1$. Thus $a\le n-1$, i.e. $n\ge a+1$. Taking the minimum over solutions gives $n_a\ge a+1$. $\square$

VERIFICATION.
  • Lemma 2 uses only the elementary inequality $\varphi(n)\le n-1$ for $n>1$.
  • Lemma 1 is the standard prime-factor identity; it shows how large ratios require many small prime factors.
  • The numerical scan is explicitly bounded and cannot resolve asymptotics.
FINAL.
UNRESOLVED.
  1. (i) Strongest proved partial result. The ratio $n/\varphi(n)$ is the multiplicative product over primes dividing $n$ (Lemma 1), and for $a=p-1$ one has $n_a=p$ so $n_a/a\to 1$ along this infinite family (Lemma 2). Any totient value $a$ satisfies $n_a\ge a+1$ (Lemma 3).
  2. (ii) First gap. Construct an explicit infinite set $\mathcal{A}$ of totient values for which the minimal preimage $n_a$ necessarily has $n_a/a\to\infty$, or prove that such a set cannot exist.
  3. (iii) Top 3 next moves. $1$ Seek a family of totient values $a$ whose preimages must include many small primes (forcing large $n/\varphi(n)$), and then prove that no smaller $n$ can realize the same $a$. $2$ Experiment computationally with larger cutoffs to see whether $\max_{a\le X} n_a/a$ grows, and if so for which structural $a$ (highly composite, smooth, etc.). $3$ Prove structural lemmas about the minimal preimage: e.g. constraints on its prime factorization or on the largest prime factor in terms of $a$.
  4. (iv) Minimal counterexample structure. If the answer is "no", one would expect a universal function $g(a)=o(\infty)$ such that for every totient value $a$ there exists some $n\le g(a)\,a$ with $\varphi(n)=a$; a counterexample to this would be a sequence of totients $a_k$ whose all preimages satisfy $n/a_k\to\infty$.