MaxMinMax problem and sparse equations over finite fields (Q285259): Difference between revisions

Let \(\mathbb F_q\) be the finite field with \(q\) elements and \(\mathcal X=\{ x_1, \ldots ,x_n\}\) be a set of variables. Consider a 3-sparse system of equations \[ f_1(X_1)=0, \ldots , f_m(X_m)=0, \] where each \(X_i\subset\mathcal X\), \(|X_i|\leq 3\) and the \(f_i\) are polynomials over \(\mathbb F_q\). The main result is that if \(m=n\) and the polynomials are taken independently and uniformly at random from the set of polynomials of degree \(\leq q-1\) in each variable then the average time complexity of finding all solutions in \(\mathbb F_q\) to the system has the upper bound \[ \frac{n}{q^{5.7883}}+\mathcal O(\log n). \] The underlying algorithm is the Gluing Algorithm introduced by the author in a previous paper [Des. Codes Cryptogr. 49, 47--60 (2008; Zbl 1196.11171); Math. Comput. Sci. 7, No. 3, 321--339 (2013; Zbl 1343.94080)]. This leads to needing an estimate on \[ \max_{\mathcal X}\min_{\pi}\max_{k} |\cup_{j=1}^k X_{\pi (j)}|-k, \] for permutations \(\pi\), an example of the \(\ell\)-MaxMinMax problem. The bulk of the paper consists of getting such an estimate.