There is this really nice paper by J.P.Serre on the congruence subgroup property for $SL_2$ for $S$-arithmetic groups (https://www.jstor.org/stable/1970630). If one looks at the proof of Proposition 3 there, Serre in fact proves the following result.

Let $a,b \in {\mathbb N}$ be two co-prime integers, and $\phi$ be Euler's totient function. For each $x\in {\mathbb N}$ we may consider $\phi (ax+b)$. Now consider the g.c.d. of the infinite set of numbers
$$N(a,b)= g.c.d. \{ \phi (ax+b): x=1,2,3,\cdots \}.$$ Now $N(a,b)$ seemingly depends on $a,b$ but it does not much: $N(a,b)$ divides $8$.

The proof of this uses Dirichlet's theorem on infinitude of primes.

If ${\mathbb Q}$ is replaced by a number field $K$, and $a,b$ are co-prime integers, define $\phi (ax+b)$ to be the number of units in the quotient ring $O_K/(ax+b)$, then the analogous g.c.d. divides $2\mu _K^2$ where $\mu _K$ is the number of roots of unity in $K$.

My question is : if I replace the linear polynomial $ax+b$ by any polynomial $P(x)=a_0+ a_1x+\cdots+ a_nx^n$, with the numbers $a_0,a_1, \cdots, a_n$ co-prime and $a_n\neq 0$, then does the corresponding g.c.d. $$g.c.d \{\phi (P(x)):x=0,1,2,..\}$$ depend (i.e. is bounded by a constant dependent) only on the degree $n$ and not on the polynomial?

The question came up in a question on discrete groups, which could be resolved, but THIS question remained. I do not have any applications for this, but I thought it was interesting on its own.

[Edit] I should have added the link https://arxiv.org/abs/math/0409377.

[Edit] The following paper https://arxiv.org/abs/1909.10808 answers this affirmatively (unconditionally for $n=2$ and modulo a well known conjecture in the general case). So the answer is Yes.

  • $\begingroup$ Did you try any experiments? $\endgroup$ – Igor Rivin Nov 19 '12 at 14:16
  • $\begingroup$ Nice question. Did you try some numerical experiment? $\endgroup$ – Joël Nov 19 '12 at 14:16
  • 1
    $\begingroup$ It can still depend on a,b even though it only takes values +/- 0,1,2,4,8. Think of Mobius function $\mu(n) = 0, \pm 1$. $\endgroup$ – john mangual Nov 19 '12 at 15:56
  • 1
    $\begingroup$ Yes, but not in a serious way; as I have said, I am interested in an upper bound on the g.c.d. independent of $a,b$ $\endgroup$ – Venkataramana Nov 19 '12 at 16:07
  • 1
    $\begingroup$ I think the right assumption to make on the polynomial is that it be irreducible over $\mathbb{Z}.$ $\endgroup$ – Igor Rivin Nov 19 '12 at 21:41

I have made some computations which seem to corroborate the OP's conjecture, namely that for any $n$ there exists a $N$, such that for every polynomial $P$ of degree $n$, with positive integral coefficients and content 1, the quantity $$g(P):= g.c.d(\phi(P(x)),x \geq 1)$$ divides $N$.

For $n=1$, as the OP says, one can take $N=8$ as proved by Serre.

For $n=2$, it seems that one can take $N=2^4 3^2 = 144$. It seems even more that one cannot do better, because for $P(x)=16x^2+32x+17$, I get experimentally $g(P)=16$ (this must not be hard to prove but I haven't tried), and for $P(x)=27 x^2 + 9x+1$, I get $g(P)=18$. So $144 | N$. On the other hand I have need been able to find any $P$ such that $g(P)$ was not a divisor of $144$.

For $n=3$ or $n=4$, I have failed to find any $P$ with $g(P)\geq 2$. This suggests $N=2$ in these cases.

| cite | improve this answer | |
  • 1
    $\begingroup$ If $P(x) | Q(x)$ then $g(P) | g(Q)$. So $(x+1)(16 x^2 + 32 x + 17)$ will achieve $144$. (By one of Gauss's many lemmas, the product of polynomials with content $1$ have content $1$.) As Igor Rivin suggests, this makes it seem natural to only study $g$ for irreducible $P$. $\endgroup$ – David E Speyer Dec 4 '12 at 15:55
  • $\begingroup$ Let $P(x)=x^4+x^3+x^2+x+1$ and $Q(x) = P(x+1)$. I claim that $5 | g(Q)$. (In fact, $g(Q)=10$.) More precisely, I'll show that any prime dividing $P(x)$ is either $1 \mod 5$ or equal to $5$. So we either have $P(x)=1$, $P(x)=5$ or $5 | \phi(P(x))$. The $+1$ makes $Q(x)$ large enough to exclude the first two. (continued) $\endgroup$ – David E Speyer Dec 4 '12 at 17:33
  • $\begingroup$ Proof of claim: If $p | x^4+x^3+x^2+x+1$ then $x$ is a $5$-th root of unity modulo $p$. Except when $p=5$, the polynomials $x-1$ and $x^4+x^3+x^x+x+1$ are relatively prime mod $p$, so $x$ is a primitive $5$-th root of unity mod $p$. This implies $p \equiv 1 \mod 5$. $\endgroup$ – David E Speyer Dec 4 '12 at 17:39
  • 1
    $\begingroup$ My intuition is that this sort of cyclotomic field trickery is basically the only way to force $g(P)$ to be large, and this trickery can clearly only get a finite amount for fixed $\deg P$. But I have no idea how to prove, or even rigorously formulate, this guess. $\endgroup$ – David E Speyer Dec 4 '12 at 17:40
  • $\begingroup$ Thanks Joel (sorry: I cannot type the umlaut). The computations look very promising. $\endgroup$ – Venkataramana Dec 9 '12 at 0:05

[I assume that by "$a_i$ coprime" you mean that the $a_i$ have no common divisor, and not that they are pairwise coprime. That would make things tricky.]

Given a collection of Sophie Germain primes ($p_i$ such that $2p_i+1$ is a prime), we can construct families where the gcd grows exponentially in $n$, with $n$ the sum of the larger primes in each pair.

First, Fermat's little theorem tells us that $2p+1$ divides $x^{2p+1} - x$ for any integer $x$. Take $x^{2p+1} + (p-1)x$ if you want to use only natural numbers. Then $\phi(2p+1) = 2p$ divides $\phi(x^{2p+1} - x)$ for all $x$. From here, we let $P(x) = \Pi(x^{2p_i+1} - x)$ for some collection of Sophie Germain primes $p_i$. Then $\Pi p_i$ divides the gcd, and the degree is $\Sigma(2p_i + 1)$

| cite | improve this answer | |
  • $\begingroup$ Your observation is compatible with the possibility that the gcd of the $\varphi$-values is bounded by a constant depending only on the degree of the polynomial. $\endgroup$ – KConrad Nov 19 '12 at 21:32
  • $\begingroup$ Of course, it is not known whether there exists an infinite collection of Sophie Germain primes :( $\endgroup$ – Igor Rivin Nov 19 '12 at 21:33
  • $\begingroup$ Yes, I do mean that $a_0{\mathbb Z}+\cdots+a_n{\mathbb Z}={\mathbb Z}$. In other words, the coefficients of $P$ do not have a common factor. $\endgroup$ – Venkataramana Nov 20 '12 at 2:30

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.