2
$\begingroup$

Euler’s totient function $\varphi$ is a function defined over $\mathbb{N}$ so that $\varphi(n)=|\{m\mid m<n\wedge (m,n)=1\}|$.

Now Lehmer’s totient problem asks whether $n$ is prime iff $\varphi(n)$ divides $n-1$.

I am curious whether the question can be expressed as a question in ring language. More specifically, whether there is a firs order formula $\psi(x)$ in the ring language so that $\mathbb{Z}\models \psi(n)$ if and only if $\varphi(n)$ divides $n-1$.

Remark As James pointed out, the question has a positive answer. But what I really want is an algebraic answer. Probably the question was not in a proper shape. How about this:

Whether there is a first order formula $\psi(x,y)$ in the ring language so that there is theory $A$ extending axioms of ring theory in a proper way (which is not necessary consistent with theory of $\mathbb{Z}$) so that

(1). $ A\vdash\forall x\exists y\psi(x,y)\wedge (\forall x \forall y(\psi(x,y)\rightarrow( y\mbox{ divides } x-1\leftrightarrow x\mbox{ is prime})) ) $; and

(2). For all $m$ and $n$, $\mathbb{Z}\models \psi(n,m)$ if and only if $m=\varphi(n)$.

$\endgroup$
  • 2
    $\begingroup$ Would it work to say something like: there exist $x_1,\dotsc,x_6$ such that $n-m=x_1^2+\dotsb+x_4^2$, $n\neq m$, and $mx_5+nx_6=1$? $\endgroup$ – Zach Teitler Feb 27 at 9:59
  • 2
    $\begingroup$ For the new question, let $\alpha$ be any sentence true in $\mathbb Z$ that is independent of the theory of rings, let $\psi_0(x,y)$ be any formula defining $y=\varphi(x)$ in $\mathbb Z$ as in James’s answer, and put $\psi(x,y)=\psi_0(x,y)\land\alpha$ and $A={}$ the theory of rings ${}+\neg\alpha$. $\endgroup$ – Emil Jeřábek Feb 28 at 8:50
  • $\begingroup$ Why (1) is satisfied? $\endgroup$ – 喻 良 Feb 28 at 8:53
  • $\begingroup$ Because in $A$, $\psi(x,y)$ implies a contradiction. $\endgroup$ – Emil Jeřábek Feb 28 at 9:50
  • 3
    $\begingroup$ This is not going to help. Put, say, $\psi_1(x,y)=(x\text{ is prime}\land y=1)\lor(x\text{ is not prime}\land y=0)$ and $\psi(x,y)=(\alpha\land\psi_0(x,y))\lor(\neg\alpha\land\psi_1(x,y))$. $\endgroup$ – Emil Jeřábek Feb 28 at 13:36
4
$\begingroup$

Yes. Every computable relation on $\mathbb{Z}$ can be defined with a first-order formula in the language of rings.

The idea is to "arithmetize" computation: encode Turing machines and their states as natural numbers in such a way that the basic operations like changing the state of the head, writing a bit, etc. are all given by arithemtic relations. This is the basis of Kleene's proof of Godel's incompleteness theorem (Godel's proof used the arithmetization of syntax, rather than computation).

$\endgroup$
  • $\begingroup$ Ah, you are right. But this is not what I want. I need a natural way to translate this. $\endgroup$ – 喻 良 Feb 27 at 8:10
  • 1
    $\begingroup$ If you are changing your question, you should do that as an edit to the body of the question, not as a comment on an answer. Or, you should post a new question, asking what you now realize you ought to have asked (and linking each question to the other). $\endgroup$ – Gerry Myerson Feb 27 at 11:39
  • 2
    $\begingroup$ @喻良 If you do wish to edit a question or ask a new one with clarification, then you should explain what you mean with "natural". $\endgroup$ – Wojowu Feb 27 at 16:07
  • $\begingroup$ I accept the answer. $\endgroup$ – 喻 良 Mar 1 at 1:05
2
$\begingroup$

For a more algebraic approach, we can add $\phi$ to the language of rings, and then state Lehmer's conjecture as:

$$(\text{axiom for } \phi)\ \&\ \phi(n)|(n-1) \implies Prime(n)$$

Here $Prime$ is one of a few defintions in the language of rings alone:

\begin{align} x|y &:= \exists u \ ux=y \\ Prime(p) &:= \forall t\ t|p \implies p|t \vee t|1 \\ Power(p,q) &:= \forall t\ t|q \implies p|t \vee t|1 \\ RelPrime(q,r) &:= \forall t\ t|q\ \&\ t|r \implies t|1 \\ PosPrime(p) &:= Prime(p) \ \& \ \phi(p)=p-1 \end{align}

And the axiom for $\phi$ is the universally quantified conjunction of

\begin{align} (p=0) \vee (p|1) &\implies \phi(p)=p\\ Prime(p) &\implies \exists u\ u|1 \ \& \ \phi(up)=up-1 \\ Power(p,q) &\implies \phi(pq)=p \phi(q) \\ RelPrime(q,r) &\implies \phi(qr)=\phi(q)\phi(r) \\ \end{align}

If $\mathbb{Z}$ satisfies the conjecture, we can ask what induction axioms are necessary to prove it.

In any case, we can ask what other rings have functions $\phi$ which satisfy the conjecture in one of these forms.

Update: To make this more recognizable as Lehman's conjecture, we should also ensure that the axioms determine the value of $\phi$ for every element in $\mathbb{Z}$. The axioms above leave open whether $\phi(2)=2-1$ or $\phi(-2)=-2-1$, which lead to $\phi(2)=1$ or $\phi(2)=3$ respectively. The values of $\phi$ for 3 and higher primes are also independent of this axiom and this choice.

We have at least three ways to determine $\phi$ completely in $\mathbb{Z}$ if we want to: either by adding the infinite set of axioms $$\{ PosPrime(2),\ PosPrime(3),\ PosPrime(5),\ PosPrime(7),\ \ldots\}$$ or by working with ordered rings and using the axiom $$1<p\ \&\ Prime(p) \implies PosPrime(p)$$ or by adding the single axiom $$PosPrime(2) \ \&\ PosPrime(3) \ \&\ PosPrime(5) \ \&\ \Big(Prime(p+q+r) \implies$$ $$(PosPrime(p) \ \&\ PosPrime(q) \ \&\ PosPrime(r)) \implies PosPrime(p+q+r)\Big)$$

I like the single axiom, but you can decide which gives the conjecture the most ring-theoretic look.

$\endgroup$
  • $\begingroup$ Thanks, this does look more algebraic. However, as you said, to prove $\phi$ is exactly Euler's function, we need some complex induction axioms. Is there definition of $\varphi$ so that Lehmer's problem holds for the polynomial ring over $Q$? $\endgroup$ – 喻 良 Mar 13 at 2:23
  • $\begingroup$ I think there is a definition of $\phi$ which makes this hold in $Q[x]$; let $\phi(q)=q$ for $q\in Q$, and $\phi(p(x))=p(x)-1$ for any monic irreducible $p$. But it would hold trivially because the hypothesis $\phi(p)|p-1$ would only be satisfied in the trivial cases. $\endgroup$ – Matt F. Mar 18 at 18:42

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.