A new criterion for the absolute irreducibility of multivariate polynomials over finite fields Carlos Agrinsoni, Heeralal Janwa, Moises Delgado Abstract A key property of an algebraic variety is whether it is absolutely irreducible, meaning that it remains irreducible over the algebraic closure of its defining field, and determining absolute irreducibility is important in algebraic geometry and its applications in coding theory, cryptography, and other fields. Among the applications of absolute irreducibility are bounding the number of rational points via the Weil conjectures and establishing exceptional APN and permutation properties of functions over finite fields. In this article, we present a new criterion for the absolute irreducibility of hypersurfaces defined by multivariate polynomials over finite fields. Our criterion does not require testing for irreducibility in the ground or extension fields, assuming that the leading form is square-free. We just require multivariate GCD computations and the square-free property. Since almost all polynomials are known to be square-free, our absolute irreducibility criterion is valid for almost all multivariate polynomials. 1 Introduction One of the most important problems in algebra and algebraic geometry is to test when a polynomial is irreducible (respectively, absolutely irreducible). Developing practical criteria to test irreducibility and absolute irreducibility is essential for applications in pure and applied mathematics. For polynomials in one variable, the Eisenstein criterion is a classical method to test irreducibility [ 25 ] . This criterion has been generalized to test the irreducibility (and, in some cases, absolute irreducibility) of multivariate polynomials using Newton polygons, prime ideals and valuations (see, for example, [ 15 , 47 , 43 ] ). The absolute irreducibility property has many applications in different areas of mathematics such as algebraic geometry, combinatorics [ 52 ] , coding theory [ 51 , 35 , 36 ] , cryptography [ 31 ] , finite geometry [ 32 , 33 ] , function field sieve [ 1 ] , permutation polynomials [ 46 ] and scattered polynomials [ 11 ] . Deep results such as the Weil, Deligne, and Bombieri bounds on the number of rational points and exponential sums require that the underlying variety be absolutely irreducible (for singular curves, see [ 9 ] ). The Weil conjectures play an essential role in applications to bound the number of rational points and exponential sums. Moreover, Deligne’s Theorem that gives bounds on rational points requires that the underlying variety is absolutely irreducible [ 23 ] . Generalizations of Weil’s conjectures to singular curves require that the polynomial defining the singular curve be absolutely irreducible [ 9 ] . The following concrete applications are particularly relevant to our results. In coding theory and cryptography, significant advances have been made in proving the exceptional conjecture of APN by demonstrating that a certain variety, defined by the corresponding multivariate polynomial, is absolutely irreducible or contains an absolutely irreducible component [ 31 ] . This conjecture was formulated for monomial functions by Janwa and Wilson [ 35 ] with significant progress. Their investigation showed that one of the existing absolute irreducibility testing criteria was effective, and they developed new methods. After half a decade, Janwa gave an absolute irreducibility criterion based on Bezout’s Theorem and intersection multiplicities. This led to significant progress by Janwa, McGuire, and Wilson [ 36 ] who mostly settled the conjecture. After two decades, it was finally proved by Hernando and McGuire [ 32 ] . Aubry, McGuire, and Rodier [ 8 ] generalized this conjecture for arbitrary functions over finite fields and the existence of an absolutely irreducible factor for the corresponding variety. In this article, we consider hypersurfaces defined by a multivariate polynomial. There exist only a few criteria for testing the absolute irreducibility of a polynomial. The method of Newton polygons generalizes the Eisenstein criterion in two different ways: 1) Eisenstein-Dumas criterion [ 24 , 55 ] ; 2) the Stepanov criterion (sometimes called the Stepanov-Schmidt criterion) [ 48 , 49 , 50 ] . A more general criterion uses Newton polytopes [ 27 ] . Other criteria are given in [ 40 , 53 , 30 , 13 , 14 , 45 , 38 , 39 , 41 , 44 , 56 , 42 ] . However, in proving absolute irreducibility theorems, these algorithms are often not practical. Indeed, the general criterion of Gao is, in general, impractical, as the algorithm requires the indecomposability of polytopes and is known to be an NP-complete problem [ 27 ] . The test of absolute irreducibility that we present here has been very effective in proving substantial parts of the APN conjecture (see [ 5 , 7 ] ). Our strategy is reminiscent of the absolute irreducibility criteria developed by Janwa and Wilson [ 35 ] . Janwa, McGuire, and Janwa give a highly effective method [ 35 , 36 ] using Bezout’s theorem and intersection multiplicities. This method has been used to settle the Segre-Bartocci conjecture [ 32 ] , and to reduce the general exceptional APN conjecture to exponents in the odd case involving only the Gold and Kasami-Welch cases. The criteria of [ 35 , 8 ] have applications to the exceptional APN conjecture, to the Segre-Bartocci conjecture [ 32 ] , and to the e. Aubry, McGuire, and Rodier [ 8 ] reduce such problems in three dimensions to two dimensions by hyperplane intersections for applications to the general exceptional APN function conjecture. The criterion we present here is an important addition to the proof of the exceptional APN conjecture, among other applications. One of the conditions to define algebraic geometric codes is that the underlying curve is absolutely irreducible [ 34 ] . In finite geometry, the Segre-Bartocci conjecture was settled by proving that a multivariate polynomial contains an absolutely irreducible factor over the defining field. Absolute irreducibility is fundamental to proving that a permutation polynomial is exceptional Our previous results are given in [ 21 , 2 ] . We also prove results on the existence of absolutely irreducible factors over the defining field. This factor guarantees a sufficient number of rational points by the bounds of Weil, Deligne, Bombieri, and Lachaud-Ghorpade (see [ 8 , 35 ] ), in proving the Segre-Bartocci conjecture [ 32 ] and the exceptional planar conjecture [ 10 ] , the exceptional APN function conjecture, among others. The article is organized as follows. In Section 2 , we provide a background. In Section 3 , we prove the main result of this article that gives an absolute irreducibility criterion (Theorem 8 ). In Section 4 , we generalize the concept of degree-gap, which helps us improve our earlier bound on the number of absolutely irreducible factors. As a consequence, we obtain a direct proof of the absolute irreducibility of a class of multivariate polynomials. The final section contains the conclusions. 2 Background A multivariate polynomial G(\textbf{X}) in \mathbb{F}(\textbf{X}):=\mathbb{F}[X_{1},\dots,X_{n}] is called absolutely irreducible if it remains irreducible over every extension of \mathbb{F} . Furthermore, in the graded degree homogeneous decomposition (in the decreasing degree order), G(\textbf{X}) decomposes as G(\textbf{X})=G_{d}(\textbf{X})+G_{d_{1}}(\textbf{X})\dots+G_{d_{m}}(\textbf{X}), (1) where G_{d_{i}}(\textbf{X}) is a non-zero homogeneous polynomial of degree d_{i} , 1\leq i\leq m , and d>d_{1}>\cdots>d_{m} . In the rest of the article, polynomials will be written in decreasing degree homogeneous forms. The homogeneous component G_{d_{m}}(\textbf{X}):=T_{G}(\textbf{X}):=T(\textbf{X}) is called the tangent cone of G . Recently, in [ 2 ] we formalized the techniques used by Aubry, McGuire, and Rodier [ 8 ] ; Ferard [ 26 ] ; and Delgado and Janwa [ 17 , 16 , 18 , 20 , 19 , 22 ] to factor a polynomial in which the leading form is square-free. In this formalism, we introduce the concept of the degree-gap of a polynomial as follows. Definition 1 Let F(\textbf{X})\in\mathbb{F}[X_{1},\dots,X_{n}] be a polynomial of degree d with at least two terms. We define the degree-gap \gamma(F) as the difference d-d_{1} from the decomposition in Equation ( 1 ). If F(\textbf{X}) is a homogeneous polynomial, then \gamma(F) is defined as infinity. Theorem 2 (Agrinsoni, Janwa & Delgado [ 2 ] ) Let F(\textbf{X})=F_{d}(\textbf{X})+H(\textbf{X})\in\mathbb{F}[\textbf{X}] . If F_{d}(\textbf{X}) is square-free, then every factor of F(\textbf{X}) has degree-gap at least \gamma(F(\textbf{X})) . Lemma 3 (Agrinsoni, Janwa & Delgado [ 2 ] ) Let F(\textbf{X})=F_{d}(\textbf{X})+H(\textbf{X})\in\mathbb{F}[\textbf{X}] . If F_{d}(\textbf{X}) is square-free and (F_{d},H)=1 , then F(\textbf{X}) has at most \left\lfloor\frac{\deg(F)}{\gamma(F)}\right\rfloor factors. In section 4 , we generalize the concept of the degree-gap of a multivariate polynomial, by introducing the i^{th} -degree-gap of the polynomial. Moreover, in Theorem 12 we give sufficient conditions to guarantee that the factors of a polynomial have at least one of the gaps of the same number as the i^{th} -degree-gap of the original polynomial. This theorem generalized Theorem 2 . As a direct consequence of this result, we generalize Lemma 3 , which bounds the number of factors of a polynomial with a square-free leading form and without homogeneous factors. A result on the absolute irreducibility of a special class of trinomials was given by Beelen and Pellikaan [ 12 ] . Recently we investigated the absolute irreducibility of multivariate polynomials with few forms with square-free leading form see propositions ( 4 , 5 , and 6 ). In this article, in Theorem 8 we give a general criterion to test absolute irreducibility. The propositions below (our earlier results ( 4 , 5 , and 6 )) are now a direct consequence of our theorem. Proposition 4 (Agrinsoni, Janwa & Delgado [ 2 ] ) Let F(\textbf{X})=F_{d}(\textbf{X})+F_{m}(\textbf{X})\in\mathbb{F}[X_{1},\dots,X_{n}] , where \deg(F)=d . If F_{d}(\textbf{X}) is square-free and (F_{d},F_{m})=1 , then F(\textbf{X}) is absolutely irreducible. This proposition provides a complete characterization of generalized binomials when the leading form is square-free. Proposition 5 (Agrinsoni, Janwa & Delgado [ 3 ] ) Let F(X)=F_{d}(X)+F_{d-e}(X)+F_{a}(X)\in\mathbb{F}[X] , where d-e>a . If F_{d}(X) is square-free, (F_{d}, F_{d-e},F_{a})=1 , and a\neq d-me for some m\in\mathbb{Z} , then F(X) is absolutely irreducible. Proposition 6 (Agrinsoni, Janwa & Delgado [ 4 ] ) Let F(\textbf{X})=F_{d}(\textbf{X})+F_{d-\gamma_{1}}(\textbf{X})+F_{d-\gamma_{2}}(\textbf{X})+F_{d-\gamma_{3}}(\textbf{X})\in\mathbb{F}[\textbf{X}] . Let F_{d}(\textbf{X}) be square-free and (F_{d},F_{d-\gamma_{1}}, F_{d-\gamma_{2}},F_{d-\gamma_{3}})=1 . If \gamma_{3}\notin\text{span}_{\mathbb{N}}\{\gamma_{1},\gamma_{2}\} , then F(\textbf{X}) is absolutely irreducible. In this article, we show that many more multivariate polynomials with square-free leading form are absolutely irreducible. The following result shows that our criterion is valid for almost alll multivariate polynomials. Proposition 7 (Gao and Lauder [ 28 ] ) Most multivariate polynomials are square-free. 3 New results For the rest of this article, we assume that 0\in\mathbb{N} . Theorem 8 Let F(\textbf{X})=F_{d}(\textbf{X})+F_{d-\gamma_{1}}(\textbf{X})+\dots+F_{d-\gamma_{m}}(\textbf{X})\in\mathbb{F}[\textbf{X}] . Let F_{d}(\textbf{X}) be square-free and (F_{d},F_{d-\gamma_{1}},\dots,F_{d-\gamma_{m}})=1 . If \gamma_{m}\notin\text{span}_{\mathbb{N}}\{\gamma_{1},\gamma_{2},\dots,\gamma_{m-1}\} , then F(\textbf{X}) is absolutely irreducible. Proof 1 Assume by way contradiction that F=(P_{s}+P_{s-1}+\dots+P_{0})(Q_{t}+Q_{t-1}+\dots+Q_{0}), (2) where P_{i} (resp. Q_{j} ) is either a form of degree i (resp. j ) or zero. Now F_{d}=P_{s}Q_{t}. (3) Let k\notin\text{span}_{\mathbb{N}}\{\gamma_{1},\gamma_{2},\dots,\gamma_{m-1}\} and 0b^{\prime} and Q_{t-j}=0 for j>c^{\prime} . Since F_{d-\gamma_{m}}(\textbf{X}) is the tangent cone of F(\textbf{X}) , it is the product of the tangent cones of P and Q . Therefore, P_{s-\gamma_{m}}=0 or Q_{t-\gamma_{m}}=0 . If P_{s-\gamma_{m}}=0 , then by Equation ( 13 ), the tangent cone of P(\textbf{X}) is P_{s} . This contradicts (F_{d},F_{d-\gamma_{1}},\dots,F_{d-\gamma_{m}})=1 . Similarly, if Q_{t-\gamma_{m}}=0 , then by Equation ( 13 ), the tangent cone of Q(\textbf{X}) is Q_{t} . This contradicts (F_{d},F_{d-\gamma_{1}},\dots,F_{d-\gamma_{m}})=1 . As a direct consequence of the proof of this theorem, we conclude the following lemmas. Lemma 9 Let F(\textbf{X})=F_{d}(\textbf{X})+F_{d-\gamma_{1}}(\textbf{X})+\dots+F_{d-\gamma_{m}}(\textbf{X})\in\mathbb{F}[\textbf{X}] . Let F_{d}(\textbf{X}) be square-free and (F_{d},F_{d-\gamma_{1}},\dots,F_{d-\gamma_{m}})=1 . If \gamma_{i}\notin\text{span}_{\mathbb{N}}\{\gamma_{1},\gamma_{2},\dots,\gamma_{i-1}\} and F(\textbf{X})=(P_{s}+P_{s-1}+\dots+P_{0})(Q_{t}+Q_{t-1}+\dots+Q_{0}) , then F_{d-\gamma_{i}}=P_{s}Q_{t-\gamma_{i}}+P_{s-\gamma_{i}}Q_{t} Lemma 10 Let F(\textbf{X})=F_{d}(\textbf{X})+F_{d-\gamma_{1}}(\textbf{X})+\dots+F_{d-\gamma_{m}}(\textbf{X})\in\mathbb{F}[\textbf{X}] . Let F_{d}(\textbf{X}) be square-free and (F_{d},F_{d-\gamma_{1}},\dots,F_{d-\gamma_{m}})=1 . If k\notin\text{span}_{\mathbb{N}}\{\gamma_{1},\gamma_{2},\dots,\gamma_{m-1}\} , 0