# (Counting problem) very interesting Modular N algebraic eqs - for combinatorics-permutation experts

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?

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

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.

-
Thank you +1, let me take a look. :o) –  annie heart Apr 12 at 23:40
it does not work for the non-prime $N$ though. –  Idear Apr 12 at 23:41
The credit is given to Idear unless someone comes up with an analytic counting solution. –  annie heart Apr 13 at 19:57
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$.
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? –  annie heart Apr 12 at 23:59