I am working on a CS paper, and I got stuck at some math related parts. I hope someone could help with below equations, more specifically whether I can determine there is a generic solution for them:
I have more than $n$ equations with n variables, but the equations are modulus equivalence values rather than actual equalities. (I can adjust the number of equations within a limit, but we can assume $j \sim 2n$, where $j$ is the number of equations) i.e.:
$d_1.c_{z,0,1} + d_2.c_{z,0,2} + ….. + d_n.c_{z,0,n} = 0 ($mod $a)$
$d_1.c_{z,1,1} + d_2.c_{z,1,2} + ….. + d_n.c_{z,1,n} = 0 ($mod $a)$
$d_1.c_{z,2,1} + d_2.c_{z,2,2} + ….. + d_n.c_{z,2,n} = 0 ($mod $a)$
….
$d_1.c_{z,j,1} + d_2.c_{z,j,2} + ….. + d_n.c_{z,j,n} = 0 ($mod $a)$
where $d_i$ are unknowns and $c_{z,j,i}$ are known coefficients. For each equation $j$, we have possibly different set of $c_{z,j,i}$ coefficients, where $j$ is the equation index and $z$ is the equation set index. $z$ is added to increase equation count, in case the number of equations are not enough to solve the system.
So, if the equations was not in modulus values, it would be easy to convert into a matrix and solve. But in this case, I am kind of stuck.
I also have managed to find some additional constraints, which would probably help solving this or determining there are no possible solutions.
- $a \in [2..k],$ where $k$ is an integer we pick, with a value $k \sim log(n)$ and equations holds for all values of $a$.
- $d_i \in \{-1,0,1\}$ for all $1 \leq i \leq n$.
Now what I am trying to figure out is, is this equation system is solvable? If it is, is there any way to make it un-solvable by changing values of $k, a, z$ etc. selected numbers.
TL;DR;
I have a set of linear equations involving modular arithmetic and I am trying to figure out whether it is solvable.
NOTE: The obvious solution where $D_i=0$ is not considered as a solution for my case.
NOTE 2: If anything is not obvious or wrong, I would be happy to provide more details/explanations.
Thank you for any help or directions how to handle this.
Best Answer
We need the equations to be solvable $∀a∈[2,k]$. This means $$d_1 \cdot c_{z,0,1}+d_2 \cdot c_{z,0,2}+ \cdots + d_n \cdot c_{z,0,n} \equiv 0 \pmod{a} \tag 1$$ becomes
$$d_1 \cdot c_{z,0,1}+d_2 \cdot c_{z,0,2}+ \cdots + d_n \cdot c_{z,0,n} = k!t \tag 2$$
for some integer $t$. Since $d_i∈\{0,±1\}$ this bounds the coefficients $c_{z,α,β}$.
This implies that the inequality constructed for a single original equation
$$∑|c_{z,α,β}|≥k!,∀α,β \tag 3$$
is a a sharp bound for sufficiently large $k$.
We construct $j \sim 2n$ such sharp bounding inequalities, one for each original equation.
If $k$ does not satisfy any of those bounding inequalities of the type $(3)$ then the original equation is not solvable.