3
$\begingroup$

Experts in algebra please help: we would like to know the number of solutions for this set of six of modular N algebraic equations:

$$ (1) \quad x_1 y_2 \equiv x_2 y_1 \pmod{N}\\ (2) \quad x_1 y_3 \equiv x_3 y_1 \pmod{N}\\ (3) \quad x_4 y_1 \equiv x_1 y_4 \pmod{N}\\ (4) \quad x_2 y_3 \equiv x_3 y_2 \pmod{N}\\ (5) \quad x_2 y_4 \equiv x_4 y_2 \pmod{N}\\ (6) \quad x_3 y_4 \equiv x_4 y_3 \pmod{N} $$ Suppose that all variables are modulo $N$. Here there are eight variables in total, $x_1,x_2,x_3,x_4, y_1,y_2,y_3,y_4$.

Questions:

(a) For $N=2$, how many independent solutions there are?

(b) For $N=3$, how many independent solutions there are?

(c) For a generic prime number $N$, how many independent solutions there are?

I emphasize these questions about counting number(how many) of independent solutions, so explicit solutions for these equations are NOT required.

Hint (what I have known): the 6 constraint equations are not independent, actually the first equations (1),(2),(3) can guarantee the last three (4)(5)(6)equations. So counting the number of degrees of freedom, roughly the number of independent solutions are about

$$ \text{ the number of independent solutions} \geq N^{8-3}=N^5 $$

On the other hand, if we set all $x_1,x_2,x_3,x_4=0$, then there are free choices for $y_1,y_2,y_3,y_4$ (which provides $N^4$ solutions). Similarly, if we set all $y_1,y_2,y_3,y_4=0$ , then there are free choices for $x_1,x_2,x_3,x_4$ (which provides $N^4$ solutions, but overlap one solution such that all $x=y=0$ counted earlier once.), so roughly the number of independent solutions are about

$$ \text{ the number of independent solutions} \geq 2\;N^{4}-1 $$

So what is the exact number expression of this number of independent solutions?

$\endgroup$
3
  • 1
    $\begingroup$ the other possibility is solving it numerically or by Mathematica. mathematica.stackexchange.com/questions/45970/… $\endgroup$ Apr 12, 2014 at 22:52
  • $\begingroup$ my conjecture is that the number of independent solutions=$N^4+N^5$, can someone disprove or prove it? :o) $\endgroup$ Apr 12, 2014 at 23:02
  • $\begingroup$ Sorry, I made a mistake, yes, I agree with Idear's result. $\endgroup$
    – miss-tery
    Apr 13, 2014 at 1:01

2 Answers 2

2
$\begingroup$

I have numerically computed, there is no better intuition for me, but your guess $N^4+N^5$ is close. Let us say the number of independent solutions $\equiv Sol(N)$, then

$$ Sol(2)=46=2^4+2^5-2 $$ $$ Sol(3)=321=3^4+3^5-3 $$ $$ Sol(5)=3745=5^4+5^5-5 $$ $$ Sol(7)=19201=7^4+7^5-7 $$

thus my conjecture is that for the prime $N$ $$ Sol(N)=N^4+N^5-N $$ I hope it helps.

$\endgroup$
3
  • $\begingroup$ Thank you +1, let me take a look. :o) $\endgroup$ Apr 12, 2014 at 23:40
  • 2
    $\begingroup$ it does not work for the non-prime $N$ though. $\endgroup$
    – wonderich
    Apr 12, 2014 at 23:41
  • $\begingroup$ The credit is given to Idear unless someone comes up with an analytic counting solution. $\endgroup$ Apr 13, 2014 at 19:57
2
$\begingroup$

Modulo a prime $N$, the integers form a field. For simplicity, use conventional algebraic notation (equals, forget about modulus). Take first the case that $x_1$ and $y_1$ aren't zero, then your first three equations reduce to: \begin{align} \frac{x_2}{x_1} &= \frac{y_2}{y_1} \\ \frac{x_3}{x_1} &= \frac{y_3}{y_1} \\ \frac{x_4}{x_1} &= \frac{y_4}{y_1} \end{align} So you can define the three ratios independently ($N^3$ options), and then fix the values of $x_1$ and $y_1$ at will ($(N - 1)^2$ options), so the total is $N^3 (N - 1)^2$. If $x_1 = 0$, then either $y_1 = 0$ and $x_2$, $x_3$ are arbitrary ($N^2$ options) or $y_1 \ne 0$ ($N - 1$ possible values) and $x_2$, $x_3$, $x_4$ arbitrary ($N^3$ options).

Adding all up gives $N^3 (N - 1)^2 + N^2 + (N - 1) N^3 = N^5 - N^4 + N^2$.

$\endgroup$
3
  • $\begingroup$ It is nice you have explicit analytic result, +1. But my numerical check is also consistent with Idear's, do you know why? maybe there is some missing part in yours? Thanks. :o) $\endgroup$ Apr 12, 2014 at 23:58
  • $\begingroup$ there are tricky things that when some of $x,y$ values are zeros, we may need to be careful that Eq.(1)~(3) may not fully account Eq.(4)~(6), isn't it? $\endgroup$ Apr 12, 2014 at 23:59
  • $\begingroup$ I might have over/undercounted somewhere. $\endgroup$
    – vonbrand
    Apr 12, 2014 at 23:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .