# (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 marie heart Apr 12 '14 at 22:52
• my conjecture is that the number of independent solutions=$N^4+N^5$, can someone disprove or prove it? :o) – annie marie heart Apr 12 '14 at 23:02
• Sorry, I made a mistake, yes, I agree with Idear's result. – miss-tery Apr 13 '14 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 marie heart Apr 12 '14 at 23:40
• it does not work for the non-prime $N$ though. – wonderich Apr 12 '14 at 23:41
• The credit is given to Idear unless someone comes up with an analytic counting solution. – annie marie heart Apr 13 '14 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$.

• 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) – annie marie heart Apr 12 '14 at 23:58
• 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 marie heart Apr 12 '14 at 23:59
• I might have over/undercounted somewhere. – vonbrand Apr 12 '14 at 23:59