4
$\begingroup$

I am interested in solving, or even just deciding the existence of a solution, for a system of quadratic diophantine equations.

Let $p$ be a prime congruent to 1 modulo 8, so $ p =17$ is the first case. We want to solve the following equations inside the integers.

Let $\alpha_1,\alpha_2,...,\alpha_p$ and $\beta_1,\beta_2,...,\beta_p$ be unknowns. We understand the indices of the $\alpha$'s and $\beta$'s modulo $p$, so that e.g. $\alpha_{-1} = \alpha_{p-1}$. We have the linear dependence between the unknowns:

\begin{align} & \sum_{j = 1}^p \alpha_j = 0, \\ & \sum_{j = 1}^p \beta_j = 0 \end{align}

Moreover for all $i$ between $1$ and $p-1$ we have two quadratic equations given as: \begin{align} & \sum_{j=1}^p \alpha_j\beta_{j-i} + \alpha_{j-i}\beta_j = 0, \\ & \sum_{j=1}^p - \alpha_j\alpha_{j-i} + \beta_j\beta_{j-i} = \left\{ \begin{array}{ll} 2, & i = \pm 2 \\ 0, & i \neq \pm 2 \end{array}\right. \end{align} It is easy to see that the equations for $\pm i$ are actually the same. Additionally we have conditions on the parities: \begin{align} & \alpha_1 \equiv \alpha_{p-1} \equiv \beta_1 \equiv \beta_{p-1} \equiv 1 \mod 2, \\ & \alpha_i \equiv \beta_i \equiv 0 \mod 2, \ \ \text{if} \ \ i \neq \pm 1 \end{align}

Alternative formulation: The problem can also be formulated using symmetric quadratic forms. For this let $A$ be the $p \times p$-permutation matrix $$\begin{pmatrix} 0 & 0 & \cdots & 0 & 1 \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{pmatrix} $$

Note that $A$ has order $p$. Let $B_i = A^i + (A^i)^T$ for each $1 \leq i \leq \frac{p-1}{2}$. Writing in block form, in particular $0$ for a $0$-matrix, define for $1 \leq i \leq \frac{p-1}{2}$ the quadratic forms $$Q_i: \mathbb{Z}^{2p} \rightarrow \mathbb{Z}, \ \ x \mapsto x^T \begin{pmatrix} 0 & B_i \\ B_i & 0 \end{pmatrix}x $$ and $$R_i: \mathbb{Z}^{2p} \rightarrow \mathbb{Z}, \ \ x \mapsto x^T \begin{pmatrix} -B_i & 0 \\ 0 & B_i \end{pmatrix}x $$ Then we can formulate the equations as $$Q_i(x) = 0 \ \ \text{and} \ \ R_i(x) = 4\delta_{i,2} $$ for all $1 \leq i \leq \frac{p-1}{2}$ where $\delta_{i,j}$ is the Kronecker delta.

If this is of any help, we can completely solve the equations modulo $4$. This gives that \begin{align} & \alpha_1\beta_{p-1} + \alpha_{p-1}\beta_1 \equiv 0 \mod 4, \\ & \alpha_i + \beta_i + \alpha_{-i} + \beta_{-i} \equiv 0 \mod 4 \ \ \text{if} \ \ i \neq 0, \pm 1 \\ & \alpha_0 + \beta_0 \equiv 2 \mod 4 \end{align}

By the origin of the problem from a question on group rings, we also know that solutions exist when p is congruent to 3 modulo 4, but we have no clue when p is congruent to 1 modulo 8. We have tried some computer experiments, but found no solution and the system seems too big for a complete solution by the programs we tried.

$\endgroup$
5
  • $\begingroup$ These equations are not exactly quadratic. Making some quantities independent can be reduced to a linear system of equations. As for solving nonlinear systems of equations, there is one way to solve them. There is no point in discussing it here because any discussion on this topic is blocked on this forum. $\endgroup$
    – individ
    May 2, 2022 at 5:38
  • $\begingroup$ For some special cases, you can get a solution. The problem is that with an increase in the number of equations, the complexity of the calculation increases very much. And the formulas themselves become extremely cumbersome. Probably because of the complexity, few people use them. For some simple systems, you can write simple solutions. math.stackexchange.com/questions/1401110/… $\endgroup$
    – individ
    May 2, 2022 at 5:41
  • $\begingroup$ Dear individ, how can the equations be made linear? Of course I have tried that, but without success. I am not a number theorist, so I might be missing even some point very clear to you. Could you give some more hints? Knowing there is a solution, would solve a research problem for me, so I would be very grateful. $\endgroup$
    – margollo
    May 2, 2022 at 15:01
  • $\begingroup$ If the unknown is not squared and there are many variables. Then you can set some variables as constant. This will reduce the degree of the equation. And then use the usual Gauss method for systems of linear equations. Well... or just imagine that this is a system of linear equations. $\endgroup$
    – individ
    May 2, 2022 at 16:18
  • $\begingroup$ Ok, I see. I have tried something in this direction, but I have some new ideas now after your comment. Thanks. $\endgroup$
    – margollo
    May 3, 2022 at 9:17

2 Answers 2

3
$\begingroup$

This sketch of a half-answer is based on and is developing the ideas of Max’ answer. He works with $\mathbb Q[I,x]$ with $I^2=-1$ modulo the cyclotomic polynomial $\Phi_p(x)$. Writing $x$ as $z^4$ and $I$ is $z^p$, this is identified with the $4p$-cyclotomic field $K$, i.e., $\mathbb Q[z]$ modulo $\Phi_{4p}(z)$. In particular, Max’ $F$ is identified with an element $f\in K$.

Since his $F^\star(x) = x^{p-2}F(1/x)$, his $x^{2-p}F^\star$ is identified with $\sigma\cdot f$ for a suitable involution $\sigma$ of $K$. One can see that $σz=z^{2p-1}=-z^{-1}$ (so $σI=I$, $σx=1/x$). Denote by $N$ the norm $N(g)≔g·σg$ of $K$ over the fixed points $K_2$ of $σ$. Conclusion: Max’ equation is equivalent to $N(f) = -2(z^2+1/z^2)^2$ (with integer $f$).

Since I do not recollect what Class Field/Iwasawa Theories say exactly about this equation, I use ad hoc method: I consider solutions in cyclotomic units instead.

Since $N(I)=N(z)=-1$, $N(1+I)=2I$, and $N(1+x)=(z^2+1/z^2)^2$, it is enough to solve $N(g)=\pm I$. Recall that since $4p$ is not a power of a prime, cyclotomic units are generated (multiplicatively) by the units $1-ζ$ (for primitive roots $ζ$ of $1$ of degree $4p$), and roots of $1$ in $K$. Modulo roots of $1$, they form a lattice spanned by such $1-ζ$ with $\Im ζ>0$ and the only relation¹⁾ $\prod (1-ζ)=I^{(p-1)/2}$. (Their importance is in the fact that they have finite index in units of $K$.)

¹⁾ Indeed, if $\Pi$ is this product, then $|\Pi|^2 = \Phi_{4p}(1) = 1$ (since $\Phi_{4p}(x)(x^2+1)(x^{2p}-1)=x^{4p}-1$), and combining $1-ζ$ and $1+1/ζ$ together gives $N(1-ζ)=1/ζ-ζ$ with argument $-π/2$. Hence argument of $\Pi$ is $(p-1)π/4$.

Lemma: If $p=2r+1$, then $U:≔\prod_{k=1}^r (1-z^{2k-1})$ solves $N(U)=±I$ provided $r$ is odd. Update: moreover, if $Λ$ is the (multiplicative) lattice generated by $(1-ζ)/(1-(-ζ^{-1}))$ with primitive roots ζ in the first quadrant. then $N(Λ)=1$, and any solution modulo this lattice is $U^s$ with an odd $s$.

Indeed, the argument in the footnote above shows that $U$ is the product over primitive roots $ζ$ of $1$ of degree $4p$ in the first quadrant, hence $N(U)$ is $\Pi$. (Update: this also describes all the solutions to $N(f)=\text{unit}$ for any $p$. In particular, if $4|p-1$, then $s∉ℤ$, hence there is no solution in cyclotomic units.)

Update: here was a completely wrong “theorem” about the case $4|p-1$. The arguments above show only this:

If the index of cyclotomic units inside units of $K$ is odd, there is no solution. (While vol.1 of Lang’s Cyclotomic fields contains some info about the 2-part of this index, I’m not fluent enough to use this info. I do not even know how to find it in PARI/gp.)

$\endgroup$
5
  • $\begingroup$ Thank you! I've also embedded the problem into $4p$-cyclotomic field, but then just proceeded with computing factorization (which is quite expensive and infeasible for large $p$). The idea of viewing the equation as a norm is very neat and fruitful! Btw, can't we simply take $\rho = z^4$? $\endgroup$ Sep 15, 2022 at 17:03
  • $\begingroup$ I decided that writing ρ=z⁴ would be a bit more confusing than what I wrote. It seems that I was wrong! $\endgroup$ Sep 16, 2022 at 7:07
  • $\begingroup$ Thanks a lot for the effort! The norm formulation is indeed elegant and it's great to see there is a solution for some primes. I don't understand the last part though, could you elaborate how you "cancel" and why you use exactly these factors? My first impression was you want to build a product like $\frac{\varepsilon_{2t}}{\varepsilon_{t}}\cdot \frac{\varepsilon_{4t}}{\varepsilon_{2t}}...$, but since $\zeta^2$ is not a primitive $4p$-th root of unity, why will $N(1-\zeta^2)$ have the right shape? Also as in the end you argue up to roots of unity, why is $N(S(\zeta)) = \pm I$ and not 1 or -1? $\endgroup$
    – margollo
    Sep 16, 2022 at 14:23
  • $\begingroup$ @IlyaZakharevich: I've tried to verify the second lemma numerically for $p=73$, where $P=2^8$ and $2P\equiv 1\pmod{73}$. However, while the lemma seems to imply $N(S(z))^4 = 1$, this equality does not hold numerically. What's wrong? $\endgroup$ Sep 16, 2022 at 18:28
  • $\begingroup$ Thanks, margollo! Indeed, everything involving the norm of $1-ζ²$ is completely irreparably wrong. $\endgroup$ Oct 18, 2022 at 11:16
2
$\begingroup$

UPDATE. Using factorization $-2(x+1)^2x^{p-3}$ over the corresponding number field, I established that there are no solutions for $p=17$. Furthermore, I computationally verified that for primes $p<30$ we have solutions for all $p\equiv 3\pmod{4}$ and do not have any for $p\equiv 1\pmod{4}$.


This is just an extended comment, giving reformulation of the problem and reducing it to just $p-1$ unknowns and $p-1$ quadratic equations over the Gaussian integers.

Consider the generating polynomials: \begin{split} A(x) &:= \sum_{i=0}^{p-1} \alpha_i x^i, \\ B(x) &:= \sum_{i=0}^{p-1} \beta_i x^i. \end{split}

The linear equations $\sum_j \alpha_j = \sum_j \beta_j = 0$ are equivalent to $A(1)=B(1)=0$, i.e., both $A(x)=(x-1)\bar A(x)$ and $B(x)=(x-1)\bar B(x)$ are multiples of $x-1$.

Viewing indices modulo $p$ is equivalent to viewing the polynomials modulo $x^p - 1 = (x-1)\Phi_p(x)$, where $\Phi_p(x) := 1 + x + \dots + x^{p-1}$ is $p$-th cyclotomic polynomial.

For reciprocal polynomials (of fixed degree $p-1$) we have $A^\star(x):=x^{p-1}A(x^{-1})\equiv x^{p-1}A(x^{p-1})\pmod{x^p-1}$ and $B^\star(x):=x^{p-1}B(x^{-1})\equiv x^{p-1}B(x^{p-1})\pmod{x^p-1}$. Then the quadratic equations (under the condition $A(1)=B(1)=0$) translate into $$\begin{cases} A(x)B^\star(x) + A^\star(x)B(x) \equiv 0 \pmod{x^p-1},\\ -A(x)A^\star(x) + B(x)B^\star(x) \equiv -4x^{p-1} + 2x + 2x^{p-3} \equiv 2(x^2-1)^2x^{p-3} \pmod{x^p-1} \end{cases} $$ Dividing both congruences by $(x-1)x(\frac1x-1)=-(x-1)^2$, we get $$\begin{cases} \bar A(x)\bar B^\star(x) + \bar A^\star(x)\bar B(x) \equiv 0 \pmod{\Phi_p(x)},\\ -\bar A(x)\bar A^\star(x) + \bar B(x)\bar B^\star(x) \equiv -2(x+1)^2x^{p-3} \pmod{\Phi_p(x)}. \end{cases} $$

In terms of polynomials over Gaussian integers, we have $$F(x)F^\star(x) \equiv -2(x+1)^2x^{p-3}\pmod{\Phi_p(x)},$$ where $$F(x) := \bar B(x) + I\cdot \bar A(x)$$ is a polynomial of degree $p-2$ over the Gaussian integers.

The last congruence can be viewed as a system of $p-1$ quadratic equations on the coefficients of $F(x)$ as unknowns.

Alternatively, it can also be viewed as the identity of palindromic polynomials: $$F(x)F^\star(x) + 2(x+1)^2x^{p-3} = G(x)\cdot \Phi_p(x),$$ where the left-hand side, $G(x)$, and $\Phi_p(x)$ are palindromic polynomials of degree $2p-4$, $p-3$, and $p-1$, respectively.

$\endgroup$
5
  • $\begingroup$ Great you could answer the question by computers! If it is ok for you, I will contact you by mail for the code to try it myself. I checked all the arguments and understand them all. Though it would be nice to have a theoretical argument, it is still very satisfying to know at least there is no solution for p=17. $\endgroup$
    – margollo
    Sep 7, 2022 at 20:23
  • $\begingroup$ There is a (relatively) simple algorithm giving (sometimes) an explicit solution of your last equation. It works for all $p≡3 \mod 4$; it does not work for all $p≡5 \mod 8$. Moreover, it works for some $p≡1 \mod 8$, for example for 73, 89, 233, 281, …. The key requirement is that there is an odd power of 2 which is $±1 \mod p$. $\endgroup$ Sep 13, 2022 at 10:44
  • $\begingroup$ @IlyaZakharevich: Please describe your algorithm in a new answer. $\endgroup$ Sep 13, 2022 at 10:57
  • $\begingroup$ I made a quick-and-dirty sketch. $\endgroup$ Sep 15, 2022 at 4:51
  • $\begingroup$ @MaxAlekseyev: Unfortunately, the part about the case $4|p-1$ seems to be irreparably wrong (as noticed by margollo above). $\endgroup$ Oct 18, 2022 at 11:14

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.