Number of solutions for overdetermined system of multilinear polynomials in a finite field?

107 Views Asked by At

A multilinear polynomial is a polynomial that is linear in each of its variables. In this case, consider a system of these polynomials in the finite field $\mathbb{F}$ as follows:

$f_1(a_1, x_1, b_1)= a_1x_1 + b_1 = c_{1,1} \quad ... \quad f_1(a_1, x_m , b_1) = a_1x_m + b_1 = c_{1,m}$

$...$

$f_n(a_n, x_1, b_n)= a_nx_1 + b_n = c_{n,1} \quad ... \quad f_n(a_n, x_m , b_n) = a_nx_m + b_n = c_{n,m}$

where $a_i, b_i$ are variables for $1 \leq i \leq n$, $x_i$ is a variable for $1 \leq i \leq m$, and $c_{i,j}$ is a constant for $1 \leq i \leq n, 1 \leq j \leq m$.

We are given that this system has at least one solution and none of the equations are linear combinations of each other. Note that there are $2n+m$ variables and $nm$ equations, so the system is overdetermined. My question is how many possible solutions for such a system are there? Can we determine some sort of exponential bound?

For context, Bézout's theorem https://en.wikipedia.org/wiki/B%C3%A9zout%27s_theorem gives an exponential upper bound, however, it only applies to when the number of variables is equal to the number of equations.