Exercise 3.7.4 (Number of representations of $n$ by $x^2 + xy + y^2$)

Question

Write the canonical factorization of $n$ in the form $n = 3^\alpha \prod p^\beta \prod q^\gamma$ where the primes $p$ are of the form $3k+1$ and the primes $q$ are of the form $3k+2$. Show that $n$ is represented by $f(x,y) = x^2 + xy + y^2$ if and only if all the $\gamma$ are even. Show that for such $n$, $R_f(n) = 6 \prod_p (\beta + 1)$(*).

\bigskip
(*)The typo is corrected (R.G.).

Richard Ganaye · Accepted Answer

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof} We write the factorization of the integer $n >1$ in prime factors in the form
 $$n = 3^\alpha \prod\limits_{p\in A_n} p^{\beta(p)} \prod\limits_{q\in B_n} q^{\gamma(q)},$$
  where the primes $p \in A_n$ are of the form $3k+1$, and the primes $q \in B_n$ are of the form $3k+2$, and $\beta(p) >0$ for all $p\in A$, $\gamma(q)>0$ for all $q \in B_n$ (note that $2 \in B_n$ if $n$ is even).

\begin{enumerate}
\item[(a)] Suppose that $n$ is represented by the form $f(x,y) = x^2 + xy + y^2$, so that $n = f(a,b) = a^2 + ab + b^2$ for some integers $a,b$. Let $q $ be a prime of the form $q = 3k+2$.

Suppose that $q \mid n$. Then $q \mid 4n = 4f(a,b) = (2a+b)^2 + 3 b^2$, so $q \mid c^2 + 3d^2$, where $c = 2a +b, d = b$.

If $a^2 + ab + b^2$ is even, then $a$ and $b$ are even.

If $q
mid d$ and $q 
e 2$, write $\overline{d}$ an inverse of $d$ modulo $q$, so that $d \overline{d} \equiv 1 \pmod q$. Then $-3 \equiv (c \overline{d})^2 \pmod q$ (where $q \wedge 3 = 1$), thus $\legendre{-3}{q} = \legendre{q}{3} = 1$, therefore $q \equiv 1 \pmod 3$, which contradicts $q \equiv 2 \pmod 3$. This contradiction shows that $q \mid d$, and since $q \mid c^2 + 3 d^2$, we have also $q \mid c$. Since $q\mid 2 a + b$ and $q\mid b$, where $q \wedge 2 = 1$, we obtain $q \mid a$ and $q \mid b$.

We have proved that every prime $q$ of the form $3k+2$ (including $q = 2$) which divides $ n = a^2 + ab + b^2$ satisfies $q \mid a$ and $q \mid b$ (this is similar to Lemma 2.14).

\bigskip
Let $q \in B_n$ be a divisor of $n$ of the form $3k+2$. Suppose, for the sake of contradiction, that $\gamma(q)$ is odd, so that $\gamma(q) = 2u+1$ for some integer $u$.

Reasoning by induction, suppose that $q^j \mid a$ and $q^j \mid b$ for some $j \leq u$. Then $q^{2j} \mid n$, and 
$$\frac{n}{q^{2j}} = \left(\frac{a}{q^j}ight)^2 + \frac{a}{q^j}\, \frac{b}{q^j} +\left( \frac{b}{q^j}ight)^2 = f\left( \frac{a}{q^j}, \frac{b}{q^j}ight).$$
Since $2j + 1 \leq 2u + 1 = \gamma(q)$,  $q \mid \frac{n}{q^{2j}} =f\left( \frac{a}{q^j}, \frac{b}{q^j}ight)$, and the same reasoning shows that $q \mid  \frac{a}{q^j}, q \mid \frac{b}{q^j}$, so that $q^{j+1} \mid a$ and $q^{j+1} \mid b$.

The induction is done, which proves that $q^{u+1} \mid a$ and $q^{u+1} \mid b$, thus $q^{2u+2} \mid n$. This is a contradiction since $\gamma(q) = 2u + 1$, so $q^{2u + 2} 
mid n$.

Therefore $\gamma(q)$ is even for all $q \in B$.

\bigskip
Conversely, suppose that $\gamma(q)$ is even for every $q \in B$. We obtain a composition of the form $f(x,y) = x^2 + xy + y^2$ with itself by the following method. Let $\omega = e^{2i\pi/3} \in \C$, which satisfies $\omega^3 = 1$, and $\omega 
e 1$, thus $\omega^2 + \omega + 1 = 0$.
Then $f(a,b) = a^2 + ab + b^2 = (a - b \omega)(a - b\omega^2)$, and for all integers $a,b,c,d$,
\begin{align*}
f(a,b) f(c,d) &= [(a - b \omega)(a - b\omega^2)][(c - d \omega)(c - d\omega^2)]\
&=[(a - b \omega)(c - d \omega)][(a - b\omega^2)(c - d\omega^2)]\
&= (ac  + bd(-\omega - 1) - (bc + ad) \omega)(ac  + bd(-\omega^2 - 1) - (bc + ad) \omega^2)\
&= (ac -bd -(bc + ad + bd) \omega)(ac -bd -(bc + ad +bd) \omega^2)\
&= f(ac - bd, bc + ad + bd).
\end{align*}
This gives the composition formula
$$f(a,b) f(c,d) = f(ac - bd, bc + ad + bd).$$
For instance $3 \cdot 7 = f(1,1) f(1,2) = f(-1, 5) = (-1)^2 + (-1)5 + 5^2$.

This shows that if $n$ and $m$ are represented by $f$, then $nm$ is also represented by $f$.
First $3 = f(1,1)$ is represented by $f$. Every $p \in A$, of the form $p = 3k + 1$ is (properly) represented by $f$ by Problem 3. If $q \in B$ is of the form $q = 3k + 2$, then $q^2 = f(q,0)$ is represented by $f$.

Since $\gamma(q)$ is even for all $q \in B_n$, $n = 3^\alpha \prod\limits_{p\in A_n} p^{\beta(p)} \prod\limits_{q\in B_n} (q^2)^{\gamma(q)/2}$ is a product of integers represented by $f$, so $n$ is represented by $f$.

In conclusion, $n = 3^\alpha \prod\limits_{p\in A_n} p^{\beta(p)} \prod\limits_{q\in B_n} q^{\gamma(q)}$ is represented by $f$ if and only if $\gamma(q)$ is even for every $q \in B_n$.

\item[(b)] We suppose now that this condition is satisfied, so that $R_f(n)>0$.

For every positive integer $n = 3^\alpha \prod\limits_{p\in A_n} p^{\beta(p)} \prod\limits_{q\in B_n} q^{\gamma(q)}$, let $s(n) = |A_n|$ denote the number of distinct primes $p \equiv 1 \pmod 3$ that divide $n$.

By Theorem 3.27,
$$R_f(n) = \sum_{d^2 \mid n} r_f\left( \frac{n}{d^2} ight),$$
and by Problem 3, 
$$r_f(n)  
= 6 \cdot\frac{1}{2}\,   N(4n) = 
\left\{
\begin{array}{ll}
 6 \cdot 2^{s(n)} & 	ext{if $\alpha = 0$ or $1$, and $B_n = \varnothing$ },\
0 & 	ext{otherwise.}
\end{array}
ight.
$$
where $N(m) = \mathrm{Card}\ \{u \in [\![0, m[\![ \ \mid u^2 \equiv -3 \pmod{m}$\} for every positive integer $m$ (in particular, $N(1) = 1$).

Put $U_n = \{d \in \N^*\ : \ d^2 \mid n\}$, and $g(n) = \frac{1}{2}\sum\limits_{d \in U_n} N(4n/d^2)$, so that
$$R_f(n) = 6 \cdot \frac{1}{2} \sum_{d \in U_n} N(4n/d^2) = 6\, g(n).$$
Suppose that $n = n_1 n_2$, where $n_1 \wedge n_2 = 1$. Then the map
$$
\varphi
\left\{
\begin{array}{ccl}
U_{n_1} 	imes U_{n_2} & 	o & U_n\
(d_1, d_2) & \mapsto & d_1 d_2
\end{array} 
ight.
$$
is bijective, because $n_1 \wedge n_2 = 1$.

We prove now that $g$ is a multiplicative function.

\begin{itemize}
\item If $n$ is odd, then $n_1, n_2$ are odd. Then, using $N(4) = 2$,
\begin{align*}
g(n_1) g(n_2 ) &= \sum_{d_1 \in U_{n_1}}\frac{1}{2} N\left(4\, \frac{n_1}{d_1^2}ight) \sum_{d_2\in U_{n_2}}\frac{1}{2} N\left(4\, \frac{n_2}{d_2^2}ight)\
&=\frac{1}{4} \sum_{(d_1,d_2) \in U_{n_1} 	imes U_{n_2}} N\left(4\, \frac{n_1}{d_1^2}ight) N\left(4\, \frac{n_2}{d_2^2}ight) \
&= \sum_{(d_1,d_2) \in U_{n_1} 	imes U_{n_2}} N\left( \frac{n_1}{d_1^2}ight) N\left(\frac{n_2}{d_2^2}ight) &(	ext{since } 4 \wedge \frac{n_i}{d_i^2} = 1)\
&= \sum_{(d_1,d_2) \in U_{n_1} 	imes U_{n_2}} N\left( \frac{n}{(d_1d_2)^2}ight)&(	ext{since }  \frac{n_1}{d_1^2} \wedge \frac{n_2}{d_2^2} = 1)\
&= \sum_{d \in U_{n} } N\left( \frac{n}{d^2}ight) &(	ext{since $\varphi$ is bijective})\
&= \frac{1}{2} \sum_{d \in U_{n} } N\left( 4 \frac{n}{d^2}ight)\
&= g(n).
\end{align*}
\item If $n$ is even, then one of the two factors $n_1$ or $n_2$ is even, say $n_1$, and the other is odd, so
$$n = 2^\delta n',\qquad n_1 = 2^\delta n'_1,\qquad n_2 = n'_2,$$
where $n', n'_1,n'_2$ are odd, and $\delta \geq 1$.

Since the congruence $x^2 \equiv - 3 \pmod 8$ has no solution, $N(2^k) = 0$ if $k \geq 3$, thus $N(2^k m) = 0$ for every positive integer $m$.
    \begin{align*}
      g(n)  &= g(2^\delta n')\
      &= \frac{1}{2} \sum_{d^2 \mid 2^\delta n'} N\left( \frac{2^{\delta + 2} n'}{d^2}ight)\
      &= \frac{1}{2} \sum_{d_1^2 \mid 2^\delta}  \sum_{d_2^2 \mid n' }N\left( \frac{2^{\delta + 2}}{d_1^2} \, \frac{n'}{d_2^2} ight)\
      &=\frac{1}{2} \left ( \sum_{d_1^2 \mid 2^\delta} N\left( \frac{2^{\delta + 2}}{d_1^2}ight) ight)\left ( \sum_{d_2^2 \mid n'} N\left( \frac{n'}{d_2^2}ight) ight)
     \end{align*}
    \begin{itemize}
    \item If $\delta$ is even, then the first sum is
    \begin{align*}
      \sum_{d_1^2 \mid 2^\delta} N\left( \frac{2^{\delta + 2}}{d_1^2}ight) &= \sum_{\lambda = 0}^{ \delta / 2 } N(2^{\delta + 2 - 2 \lambda}) & (d_1 = 2^\lambda)\
      &= N(4) \
      &= 2.
    \end{align*}
    Thus $g(n ) = \sum\limits_{d^2 \mid n'} N\left( \frac{n'}{d^2}ight)$, and similarly $g(n_1) =  \sum\limits_{d_1^2 \mid n'_1} N\left( \frac{n'_1}{d_1^2}ight)$. Therefore
  \begin{align*}
  g(n_1) g(n_2) &= \sum_{d_1^2 \mid n'_1} N\left( \frac{n'_1}{d_1^2}ight) \cdot \frac{1}{2} \sum_{d_2^2 \mid n'_2}N\left(4\, \frac{n'_2}{d_2^2}ight)\
  &=\frac{1}{2}  \sum_{d_1^2 \mid n'_1}  \sum_{d_2^2 \mid n'_2} N\left(4\frac{n'_1n'_2}{(d_1d_2)^2}ight)\
  &=\frac{1}{2} \sum_{d^2\mid n'} N\left(4\frac{n'}{d^2}ight)\
  &=\sum_{d^2\mid n'} N\left(\frac{n'}{d^2}ight)\
  &= g(n).
  \end{align*}

\item If $\delta$ is odd,
    \begin{align*}
     \sum_{d_1^2 \mid 2^\delta} N\left( \frac{2^{\delta + 2}}{d_1^2}ight) &= \sum_{\lambda = 0}^{\lfloor  \delta / 2 floor } N(2^{\delta + 2 - 2 \lambda}) &(	ext{where } \lfloor  \delta / 2 floor = (\delta - 1)/2)\
     &= N(2^3)+ N(2^4)+ \cdots\
     &= 0.
    \end{align*}
    Thus $g(n) = 0$, and similarly $g(n_1) = 0$, so $g(n) = g(n_1)g(n_2)$.
    \end{itemize}
\end{itemize}
In all cases,
$$n_1 \wedge n_2 = 1 \Rightarrow g(n_1n_2) = g(n_1) g(n_2).$$

Since $g$ is a multiplicative function, for $n = 3^\alpha \prod\limits_{p\in A_n} p^{\beta(p)} \prod\limits_{q\in B_n} q^{\gamma(q)}$, we obtain
\begin{align}
R_f(n) &= 6g(n) = 6 \,  g(3^\alpha) \prod\limits_{p\in A_n} g(p^{\beta(p)}) \prod\limits_{q\in B_n} g(q^{\gamma(q)}).
\end{align}
We evaluate the values  $g(p^k)$ for the three types of prime numbers in this formula.
\begin{itemize}
\item If $p=3$, $N(3^0) = N(3^1) = 1$ and $N(3^k) = 0$ if $k \geq 2$, because $u^2 \equiv -3 \pmod {3^k}$ implies $3 \mid u$, so $u = 3v$ for some integer $v$, and $v^2 \equiv -1 \pmod{3^{k-1}}$, where $k-1 \geq 1$, thus $v^2 \equiv -1 \pmod 3$. This is impossible, thus $N(3^k) = 0$ for $k \geq 2$. This gives
\begin{align*}
g(3^\alpha) &= \frac{1}{2} \sum_{d^2 \mid 3^\alpha} N\left(4\,  \frac{3^\alpha}{d^2}ight)\
&=\sum_{d^2 \mid 3^\alpha} N\left(\frac{3^\alpha}{d^2}ight) &(	ext{since } 4 \wedge (3^\alpha/d^2 = 1) \
&=\sum_{\mu = 0}^{\lfloor \alpha/2 floor} N(3^{\alpha - 2 \mu})& (d = 3^\mu)\
&= 
\left\{
\begin{array}{ll}
N(3) & 	ext{if $\alpha$ is odd,}\
N(1) & 	ext{if $\alpha$ is even}
\end{array}
ight.
\end{align*}
In both cases, $$g(3^\alpha) = 1.$$

\item If $ p \equiv 1 \pmod 3$, then $\legendre{-3}{p} = \legendre{p}{3} = 1$, so the congruence $x^2 \equiv  \-3 \pmod p$ has two solutions, thus $N(p) = 2$. By Hensel's Lemma, $N(p^\beta) = 2$ for $\beta \geq 1$ (and $N(p^0) = 1$).

Here $p$ is an odd prime, so
\begin{align*}
g(p^\beta) &= \frac{1}{2} \sum_{d^2 \mid p^\alpha} N\left(4\,  \frac{p^\beta}{d^2}ight)\
&=\sum_{d^2 \mid p^\beta} N\left(\frac{p^\beta}{d^2}ight)\
&= \sum_{
u = 0}^{\lfloor \beta/2 floor} N(p^{\beta - 2 
u})&(d = p^
u)\
&= 
\left\{
\begin{array}{ll}
 N(1) + N(p^2) + \cdots + N(p^\beta) & 	ext{if $\beta$ is even},\
  N(p) + N(p^3) + \cdots + N(p^{\beta}) & 	ext{if $\beta$ is odd.}
\end{array}
ight.
\end{align*}
Since $N(p^\beta) = 2 (\beta>1)$ and $N(1) = 1$, we obtain 
\begin{align*}
g(p^\beta) = 1 + 2 \frac{\beta}{2} = \beta + 1 	ext{ if $\beta$ is even},\
g(p^\beta) = 2 (\frac{\beta + 1}{2} = \beta + 1 	ext{ if $\beta$ is odd}.
\end{align*}
In both cases,
$$g(p^\beta) = \beta + 1,\qquad (p \equiv 1 \pmod 3).$$

\item If $q \equiv 2 \pmod 3$, then $\legendre{-3}{q} = \legendre{q}{3} = -1$, thus so the congruence $x^2 \equiv  \-3 \pmod q$ has no solution, a fortiori $x^2 \equiv  \-3 \pmod q^\gamma\ (\gamma \geq 1)$ has no solution. Therefore $N(q) = 0$, and $N(q^\gamma) = 0$ if $\gamma \geq 1$. Then

\begin{itemize}
\item If $q 
e 2$,
\begin{align*}
g(q^\gamma) &= \frac{1}{2} \sum_{d^2 \mid q^\gamma} N\left(4\,  \frac{q^\gamma}{d^2}ight)\
&=\sum_{d^2 \mid q^\gamma} N\left(\frac{q^\gamma}{d^2}ight)\
&= \sum_{
u = 0}^{\lfloor \gamma/2 floor} N(q^{\gamma- 2 
u})&(d = q^
u)\
&= 
\left\{
\begin{array}{ll}
 N(1) + N(q^2) + \cdots + N(q^\gamma) = 1 & 	ext{if $\gamma$ is even},\
  N(q) + N(q^3) + \cdots + N(q^{\gamma}) = 0 & 	ext{if $\gamma$ is odd.}
\end{array}
ight.
\end{align*}
By hypothesis, $\gamma(n)$ is even, thus
$$g(q^{\gamma(q)})= 1 \qquad (q 
e 2).$$
\item If $q = 2$, we have already proven that $N(2^k) = 0$ if $k \geq 3$, and $N(1) = N(2)=1, N(2^2) = 2$. Then
\begin{align*}
g(2^\gamma) &= \frac{1}{2} \sum_{d^2 \mid 2^\gamma} N\left(4\,  \frac{2^\gamma}{d^2}ight)\
&= \frac{1}{2} \sum_{d^2 \mid 2^\gamma} N\left( \frac{2^{\gamma + 2}}{d^2}ight)\
&=\frac{1}{2} \sum_{
u = 0}^{\lfloor \gamma/2 floor} N \left( 2^{\gamma + 2 - 2 
u} ight)\
&= 
\left\{
\begin{array}{ll}
  \frac{1}{2}(N(2^2) + \cdots + N(2^\gamma) + N(2^{\gamma + 2})) = 1 & 	ext{if $\gamma$ is even},\
  \frac{1}{2}(N( 2^3) + \cdots + N(2^\gamma) + N(2^{\gamma + 2})) = 0 & 	ext{if $\gamma$ is odd.}
\end{array}
ight.
\end{align*}
Since $\gamma(q)$ is even by hypothesis, we obtain the same results than in the case $q$ odd: for all $q\in B_n$, including $q = 2$,
$$g(q^{\gamma(q)})= 1.$$

\end{itemize}
\end{itemize}
With these results,  equation (1) gives for $n = 3^\alpha \prod\limits_{p\in A_n} p^{\beta(p)} \prod\limits_{q\in B_n} q^{\gamma(q)}$,
$$R_f(n) = \prod_{p \in A_n} (\beta(p) + 1).$$

\end{enumerate}
Phew!
\end{proof}
Note: I mimicked the proofs of N.Z.M. given in the case of sum of two squares. Using the decomposition of $n$ in prime factors in the Principal Ideal Domain  $\Z[\omega]$ ($\omega = e^{2i\pi/3}$), there must be a shorter proof of this last result.

Some code in Sage to check the preceding results on the functions $N$ and $g$:
\begin{verbatim}
def N(m):
    counter = 0
    for u in range(m):
        if u^2 % m == (-3) % m:
            counter += 1
    return counter
    
def g(n):
    d = 1
    som = 0
    while d^2 <= n:
        if n % (d^2) == 0:
            q = n // d^2
            som += N(4*q)
        d += 1
    assert som % 2 == 0
    return som // 2

[N(3^k) for k in range(7)]
        [1, 1, 0, 0, 0, 0, 0]
        
[g(3^k) for k in range(7)]
        [1, 1, 1, 1, 1, 1, 1]

[N(7^k) for k in range(7)]
        [1, 2, 2, 2, 2, 2, 2]

[g(7^k) for k in range(7)]
        [1, 2, 3, 4, 5, 6, 7]

[N(11^k) for k in range(7)]
         [1, 0, 0, 0, 0, 0, 0]

[g(11^k) for k in range(7)]
        [1, 0, 1, 0, 1, 0, 1]

[N(2^k) for k in range(7)]
        [1, 1, 2, 0, 0, 0, 0]

[g(2^k) for k in range(7)]
        [1, 0, 1, 0, 1, 0, 1]

\end{verbatim}
We can also verify that $g$ is a multiplicative function:
\begin{verbatim}
for x in range(1,101):
    for y in range(1,101):
        if gcd(x, y) == 1:
            if g(x * y) != g(x)* g(y):
                print('There is something wrong in the Kingdom') 
\end{verbatim}

Exercise 3.7.4 (Number of representations of $n$ by $x^2 + xy + y^2$)

Answers

Comments

Exercise 3.7.4 (Number of representations of $n$ by $x^2 + xy + y^2$)

Answers

Comments

Add answer