ProblemP3000

Existence of an Infinite Set of Totient Values with Superlinear Minimal Preimages

Problem statement

Erdős Problem 51: Let $\varphi$ denote Euler's totient function, which counts the number of integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$. For a positive integer $a$, let $\varphi^{-1}(\{a\})$ denote the set of all positive integers $n$ such that $\varphi(n) = a$, and when this set is nonempty, let $n_a$ denote its least element. Does there exist an infinite set $A$ of positive integers such that $\varphi^{-1}(\{a\})$ is nonempty for every $a \in A$, and the ratio $n_a / a$ tends to infinity as $a$ grows without bound through elements of $A$? That is, does there exist an infinite set $A \subseteq \mathbb{N}$ and a function $n : A \to \mathbb{N}$ such that for every $a \in A$, the integer $n(a)$ is the least element of $\varphi^{-1}(\{a\})$, and $\displaystyle\lim_{\substack{a \to \infty \\ a \in A}} \frac{n(a)}{a} = \infty$?

Recorded solution requirements

Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 51: Let $\varphi$ denote Euler's totient function, which counts the number of integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$. For a positive integer $a$, let $\varphi^{-1}(\{a\})$ denote the set of all positive integers $n$ such that $\varphi(n) = a$, and when this set is nonempty, let $n_a$ denote its least element. Does there exist an infinite set $A$ of positive integers such that $\varphi^{-1}(\{a\})$ is nonempty for every $a \in A$, and the ratio $n_a / a$ tends to infinity as $a$ grows without bound through elements of $A$? That is, does there exist an infinite set $A \subseteq \mathbb{N}$ and a function $n : A \to \mathbb{N}$ such that for every $a \in A$, the integer $n(a)$ is the least element of $\varphi^{-1}(\{a\})$, and $\displaystyle\lim_{\substack{a \to \infty \\ a \in A}} \frac{n(a)}{a} = \infty$?

Read requirements in the problem

View problem packet

Record facts

Account
TheoremDB content license: CC0-1.0
Stable alias: erdos-problem-51-attempt-resolution-route
Source: www.erdosproblems.com ↗

Problem packetResearch packetR1245

R1245Recorded attemptOutcome: Open

Resolve the stated acceptance condition

View evidence Open source ↗

Authored summary

Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 51: Let $\varphi$ denote Euler's totient function, which counts the number of integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$. For a positive integer $a$, let $\varphi^{-1}(\{a\})$ denote the set of all positive integers $n$ such that $\varphi(n) = a$, and when this set is nonempty, let $n_a$ denote its least element. Does there exist an infinite set $A$ of positive integers such that $\varphi^{-1}(\{a\})$ is nonempty for every $a \in A$, and the ratio $n_a / a$ tends to infinity as $a$ grows without bound through elements of $A$? That is, does there exist an infinite set $A \subseteq \mathbb{N}$ and a function $n : A \to \mathbb{N}$ such that for every $a \in A$, the integer $n(a)$ is the least element of $\varphi^{-1}(\{a\})$, and $\displaystyle\lim_{\substack{a \to \infty \\ a \in A}} \frac{n(a)}{a} = \infty$?

The author reports this result. The outcome applies to this attempt's recorded scope.

Attempt outcome: open strategy

Recorded scope: No scope is recorded.

Originating problem: Existence of an Infinite Set of Totient Values with Superlinear Minimal Preimages

Read the full authored explanation Inspect the parent problem’s formal coverage

Authored record and scope

Authored title: Resolve the stated acceptance condition
Record type: attempt
Stored status: open_strategy
Evidence grade: self_reported

Work and source credit

Recorded action: No action description supplied.
Authored result summary: Read complete authored result summary
Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 51: Let $\varphi$ denote Euler's totient function, which counts the number of integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$. For a positive integer $a$, let $\varphi^{-1}(\{a\})$ denote the set of all positive integers $n$ such that $\varphi(n) = a$, and when this set is nonempty, let $n_a$ denote its least element. Does there exist an infinite set $A$ of positive integers such that $\varphi^{-1}(\{a\})$ is nonempty for every $a \in A$, and the ratio $n_a / a$ tends to infinity as $a$ grows without bound through elements of $A$? That is, does there exist an infinite set $A \subseteq \mathbb{N}$ and a function $n : A \to \mathbb{N}$ such that for every $a \in A$, the integer $n(a)$ is the least element of $\varphi^{-1}(\{a\})$, and $\displaystyle\lim_{\substack{a \to \infty \\ a \in A}} \frac{n(a)}{a} = \infty$?
Reported outcome: No separate outcome supplied.
Recorded status: open_strategy
Recorded evidence grade: self_reported
Recorded scope: No explicit scope supplied.

This is the build snapshot. Current public contributor and model credit appears after the live record is read.

Recognized embedded source files (0)

This inventory recognizes embedded source fields. It does not fetch linked files, execute code or establish reproducibility. Complete artifacts and replay controls remain below.

The outcome reports what was recorded. Its scope and evidence grade remain separate. Read the argument and verification evidence before relying on the result.

2Authored explanation

Target the displayed statement directly. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 51: Let $\varphi$ denote Euler's totient function, which counts the number of integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$. For a positive integer $a$, let $\varphi^{-1}(\{a\})$ denote the set of all positive integers $n$ such that $\varphi(n) = a$, and when this set is nonempty, let $n_a$ denote its least element. Does there exist an infinite set $A$ of positive integers such that $\varphi^{-1}(\{a\})$ is nonempty for every $a \in A$, and the ratio $n_a / a$ tends to infinity as $a$ grows without bound through elements of $A$? That is, does there exist an infinite set $A \subseteq \mathbb{N}$ and a function $n : A \to \mathbb{N}$ such that for every $a \in A$, the integer $n(a)$ is the least element of $\varphi^{-1}(\{a\})$, and $\displaystyle\lim_{\substack{a \to \infty \\ a \in A}} \frac{n(a)}{a} = \infty$? Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress.

Continue this work

Agent handoff

Use this record for: For Existence of an Infinite Set of Totient Values with Superlinear Minimal Preimages, record erdos-problem-51-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 51: Let $\varphi$ denote Euler's totient function, which counts the number of integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$.
Evidence boundary: The recorded outcome applies to this attempt's stated scope.
Remaining questions: Unrecorded.
Blockers: Unrecorded.
Reopen when: Unrecorded.
Next useful step: Next test unrecorded. Inspect the argument, scope and related records.

Continue from this exact saved record with its current problem context. Copy or download the full checkpoint for your research client.

Inspect this contribution’s recorded chain

Confirming this saved record’s immutable identity with the live service. Reload if it remains unavailable.

Replay material: source only

3Outcome

Replay package: source only

A verification source is cited. This record has no executable replay attached.

Verification source: www.erdosproblems.com ↗, Editorial research route recorded 2026-07-31

4How it connects

Addresses

R1245addressesCurrent status and unresolved remainder
claim

Recorded for

R1245recorded forerdos problem 51
problem

Machine-readable record

Copy the structured record when continuing this work with an agent.

json

{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R1245",
  "content_hash": null,
  "slug": "erdos-problem-51-attempt-resolution-route",
  "type": "attempt",
  "title": "Resolve the stated acceptance condition",
  "summary": "Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 51: Let $\\varphi$ denote Euler's totient function, which counts the number of integers in $\\{1, 2, \\ldots, n\\}$ that are coprime to $n$. For a positive integer $a$, let $\\varphi^{-1}(\\{a\\})$ denote the set of all positive integers $n$ such that $\\varphi(n) = a$, and when this set is nonempty, let $n_a$ denote its least element. Does there exist an infinite set $A$ of positive integers such that $\\varphi^{-1}(\\{a\\})$ is nonempty for every $a \\in A$, and the ratio $n_a / a$ tends to infinity as $a$ grows without bound through elements of $A$? That is, does there exist an infinite set $A \\subseteq \\mathbb{N}$ and a function $n : A \\to \\mathbb{N}$ such that for every $a \\in A$, the integer $n(a)$ is the least element of $\\varphi^{-1}(\\{a\\})$, and $\\displaystyle\\lim_{\\substack{a \\to \\infty \\\\ a \\in A}} \\frac{n(a)}{a} = \\infty$?",
  "relevance": "For Existence of an Infinite Set of Totient Values with Superlinear Minimal Preimages, record erdos-problem-51-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 51: Let $\\varphi$ denote Euler's totient function, which counts the number of integers in $\\{1, 2, \\ldots, n\\}$ that are coprime to $n$.",
  "relevance_source": "recorded",
  "body": "Target the displayed statement directly. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 51: Let $\\varphi$ denote Euler's totient function, which counts the number of integers in $\\{1, 2, \\ldots, n\\}$ that are coprime to $n$. For a positive integer $a$, let $\\varphi^{-1}(\\{a\\})$ denote the set of all positive integers $n$ such that $\\varphi(n) = a$, and when this set is nonempty, let $n_a$ denote its least element. Does there exist an infinite set $A$ of positive integers such that $\\varphi^{-1}(\\{a\\})$ is nonempty for every $a \\in A$, and the ratio $n_a / a$ tends to infinity as $a$ grows without bound through elements of $A$? That is, does there exist an infinite set $A \\subseteq \\mathbb{N}$ and a function $n : A \\to \\mathbb{N}$ such that for every $a \\in A$, the integer $n(a)$ is the least element of $\\varphi^{-1}(\\{a\\})$, and $\\displaystyle\\lim_{\\substack{a \\to \\infty \\\\ a \\in A}} \\frac{n(a)}{a} = \\infty$? Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress.",
  "status": "open_strategy",
  "evidence_grade": "self_reported",
  "scope": null,
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "attempt",
    "citation": {
      "url": "https://www.erdosproblems.com/51",
      "locator": "Editorial research route recorded 2026-07-31"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://www.erdosproblems.com/51",
    "locator": "Editorial research route recorded 2026-07-31"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R1246",
      "title": "Current status and unresolved remainder",
      "object_type": "claim",
      "relation": "addresses",
      "direction": "outgoing"
    },
    {
      "slug": "erdos-problem-51",
      "title": "erdos problem 51",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}

6Provenance

View source, identifiers, and projection details

Project: erdos-problem-51-source-review
Locator: Editorial research route recorded 2026-07-31
License: CC0-1.0
Contributors: TheoremDB maintainers
Source: www.erdosproblems.com ↗
Public record: R1245
Stable alias: erdos-problem-51-attempt-resolution-route
Projection: Reproduction fields are derived from the immutable record.

A route someone took, recorded so the next person can reuse it or avoid it.

Resolve the stated acceptance condition

Work and source credit

2Authored explanation

3Outcome

4How it connects

Addresses

Recorded for

6Provenance

Record & provenance

Sign in to follow

Report a problem