ISSN 2148-838Xhttps://doi.org/10.13069/jacodesmath.940192 J. Algebra Comb. Discrete Appl. 8(2) • 139–149 Received: 19 July 2020 Accepted: 4 March 2021 Journal of Algebra Combinatorics Discrete Structures and Applications Algebraic methods in difference sets and bent functions Research Article Pradipkumar H. Keskar, Priyanka Kumari Abstract: We provide some applications of a polynomial criterion for difference sets. These include counting the difference sets with specified parameters in terms of Hilbert functions, in particular a count of bent functions. We also consider the question about the bentness of certain Boolean functions introduced by Carlet when the C-condition introduced by him doesn’t hold. 2010 MSC: 05B10, 6E30,13P25, 94C10, 11T71 Keywords: Hilbert functions, C-condition, Flat, Difference set, Bent functions 1. Introduction In [5], a criterion was developed for subsets of a finite abelian group to be difference sets with specified parameters. The criterion was in terms of polynomial conditions on their characteristic vectors. This opens up the possibilities of algebro-geometric methods in studying difference sets. Recall that for a finite group G of order v and integers k,λ, a subset D of G is called a difference set of G with parameters (v,k,λ), or (v,k,λ)-difference set of G, if |D| = k and |{(g1,g2) ∈ D × D : g1g−12 = g}| = λ for any non-identity element g ∈ G. This paper discusses its applications in the study of difference sets and bent functions, which are cryptographically significant. Recall that for an even positive integer t > 2, a Boolean function of t variables is a bent function if and only if its support is a difference set in (Z/2Z)t with parameters (v,k,λ) where v = 2t,k = 2(t−1)±2(t−2)/2 and λ = 2(t−2)±2(t−2)/2(where signs are chosen consistently). In Section 2, we show that the number of difference sets in an abelian group is given by the affine Hilbert function of a certain ideal in a polynomial ring. As a special case, the same holds for the number of bent functions of an even dimension. It may be pointed out that the count of bent functions is an important unresolved issue and even the known bounds for it are quite weak, see [9] for the details. It is hoped that Computer Algebra software like Macaulay2, Singular, which facilitate computation of Hilbert functions, will play a role in enhancing our knowledge in this direction. Pradipkumar H. Keskar, Priyanka Kumari (Corresponding Author); Department of Mathematics, Birla Intitute of Technology and Science, Pilani (Pilani Campus), Pilani 333031, India (email: keskar@pilani.bits-pilani.ac.in, priyanka.kumari@pilani.bits-pilani.ac.in). 139 https://orcid.org/0000-0001-5463-4189 https://orcid.org/0000-0003-4453-8518 P. H. Keskar, P. Kumari / J. Algebra Comb. Discrete Appl. 8(2) (2021) 139–149 In Section 3, the criterion of [5] is reformulated to characterize those exchanges of elements of a difference set which again lead to a difference set. The formulation is in terms of certain values of a polynomial function. In subsequent sections, this criterion is applied to establish non-bentness of an infinite familiy of certain functions introduced by Carlet in [2], which we now introduce. Let F2 = {0, 1} be the field with two elements and let m be a positive integer and t = 2m. For any x = (x1, . . . ,xm),y = (y1, . . . ,ym) ∈ Fm2 , let x · y = ∑m i=1 xiyi ∈ F2. Let L be an F2-subspace of F m 2 , L⊥ = {y ∈ Fm2 : x ·y = 0 for all x ∈ L} be the orthogonal complement of L and let 1L⊥ : Fm2 → F2 be defined by 1L⊥(x) = 1 if x ∈ L⊥ and 1L⊥(x) = 0 otherwise. For a permutation π of Fm2 , consider the function f(π,L) : Ft2 = F m 2 ×Fm2 → F2 be defined by f(π,L)(x,y) = x ·π(y) + 1L⊥(x). Carlet found a class of bent functions called C-class of bent functions. For this purpose, he introduced C-condition on (π,L) thus : (π,L) satisfies the C-condition if and only if for any a ∈ Fm2 , π−1(a + L) is a flat (i.e. an affine subspace) in Fm2 . He then showed that C-condition is sufficient for bentness of f(π,L), that is, if (π,L) satisfies C-condition then f(π,L) is a bent function. The class of bent functions obtained in this manner is called the C-class of bent functions. The C-condition was further explored in [7]. But it is not known that failure of C-condition by (π,L) implies non-bentness of f(π,L). Thus we need another machinary to prove non-bentness of f(π,L). As supports of bent functions are difference sets, the results of [5] become relevant. In this paper, we consider π defined by π(x1, . . . ,xm) = ((x1 + P(x2, . . . ,xm)),x2, . . . ,xm) for all (x1, . . . ,xm) ∈ Fm2 , where P(X2, . . . ,Xm) ∈ F2[X2, . . . ,Xm]. Thus π is induced by an important type of polynomial automorphisms of Fm2 , called elementary automorphisms, a generating set of the so called tame automorphism group, see [10]. For several classes of (π,L), we decide when the C-condition is satisfied and in some examples where it is not satisfied, we conclude the non-bentness of f(π,L). 2. Counting the difference sets Let G = ∏t l=1 ( Z nlZ ) be an abelian group and let v = |G|. For any il ∈ ZnlZ ; 1 ≤ l ≤ t, let i∗l ∈ {0, 1, . . . ,nl − 1} be such that il = i ∗ l + nlZ. For any subset T of G, α = (αg : g ∈ G) ∈ C v is called the point representation or characteristic vector of T if αg = 1 for g ∈ T and αg = 0 otherwise. Let X1, . . . ,Xt be independent variables over C and let Ag,g ∈ G be v independent variables over C[X1, . . . ,Xt]. Letting X = (X1, . . . ,Xt) and A = (Ag : g ∈ G), we define Ψ = Ψ(X,A) ∈ C[X,A] by Ψ =   ∑ (i1,...,it)∈G Ai1···itX i∗1 1 · · ·X i∗t t     ∑ (i1,...,it)∈G Ai1···itX n1−i∗1 1 · · ·X nt−i∗t t   −λ   ∑ (i1,...,it)∈G X i∗1 1 · · ·X i∗t t  − (k −λ). Further let U = {ξ = (ξ1, . . . ,ξt) ∈ Ct : ξnll = 1 for all 1 ≤ l ≤ t} and Pg(A) = A 2 g −Ag ∈ C[A] for all g ∈ G. In Theorem 3.2 of [5], we have given a polynomial criterion for (v,k,λ) difference set in G as follows : Theorem 2.1. For α = (αg : g ∈ G) ∈ Cv, α is a point representation of a (v,k,λ) difference set in G if and only if α satisfies the equations Pg(A) = 0 for all g ∈ G, and Ψ(ξ,A) = 0 for all ξ = (ξ1, . . . ,ξt) ∈ U. 140 P. H. Keskar, P. Kumari / J. Algebra Comb. Discrete Appl. 8(2) (2021) 139–149 As a consequence, (v,k,λ) difference sets in G are in one-to one correspondence with the points of the zero-dimensional affine algebraic set V (Ψ(ξ,A),Pg(A) : ξ ∈ U,g ∈ G) = {α ∈ Cv : Ψ(ξ,α) = 0 for all ξ ∈ U,Pg(α) = 0 for all g ∈ G}. This brings us to the concept of affine Hilbert function of an ideal in a polynomial ring. To define this, let R = k[Z1, . . . ,Zr] be the polynomial ring in r variables over a field k and for a non-negative integer s, let R≤s = {f(Z1, . . . ,Zr) ∈ R : deg f ≤ s}. For an ideal I of R, let I≤s = I ∩R≤s. Note that R≤s is a finite dimensional k-vector space and I≤s is its subspace. We define the affine Hilbert function of I as the integer valued function aHFI of non-negative integers such that aHFI(s) = dimk ( R≤s I≤s ) . It turns out that there is a polynomial, called affine Hibert Polynomial of I and denoted by aHPI, whose values coincide with the values of the affine Hilbert function of I for large integer values of s. Letting I(V ) = {f(Z1, . . . ,Zr) ∈ R : f(z1, . . . ,zr) = 0 for all (z1, . . . ,zr) ∈ V} for V ⊂ kr, Exercise 11 on p. 475 of [3] shows that if |V | is finite then aHPI(V ) is the constant polynomial |V |. We now apply this to V = V (Ψ(ξ,A),Pg(A) : ξ ∈ U,g ∈ G) to get the following Corollary 2.2. The number of (v,k,λ)-difference sets in the group G = ∏t l=1 ( Z nlZ ) is given by aHPJ(s) for any s ∈ C where J is the ideal of C[A] generated by {Ψ(ξ,A),Pg(A) : ξ ∈ U,g ∈ G}. Proof. In the light of the above discussion, the proof will be complete if we show that I(V (J)) = J. By Strong Hilbert Nullstellensatz (Theorem 6 on p. 176 of [3]), I(V (J)) = √ J. This reduces our work to showing that √ J = J. This follows from Theorem 8.14 on p. 343 of [1], since Pg(A) is square-free and C is perfect. Remark 2.3. In stead of the affine Hilbert Polynomial of J, we could use the Hilbert Polynomial of the homogenization Jh of J as well. In some computational software, Hilbert Polynomial of a homogeneous ideal in a graded ring is easier to deal with, hence we also give an alternate formulation of the above corollary. Let B be an indeterminate over C[A] and let C[A]h = C[A][B]. The homogenization Jh is the ideal of C[A]h generated by {fh : f ∈ J}, where for any f ∈ C[A], fh ∈ C[A]h is defined by fh(A,B) = Bdeg(f)f ( Ag B : g ∈ G ) . To obtain a finite generating set of Jh, note that by Theorem 4 on p. 388 of [3], if S is a Grob̈ner basis of J then {fh : f ∈ S} is the Grob̈ner basis of Jh. To define Hilbert Function HFJh of J h, for any non-negative integer s, consider the k-vector spaces C[A]hs = {f ∈ R h : f = 0 or f is homogeneous of degree s} and Jhs = J h∩C[A]hs. We define HFJh(s) = dimk ( C[A]hs Jhs ) . By Theorem 12 on p. 464 of [3], aHFJ(s) = HFJh(s) for all non-negative integers s. This allows us to replace the affine Hilbert Function aHFJ by the Hilbert Function HFJh(s). Remark 2.4. Corollary 2.2 also gives a count of all bent functions of t variables. Since the set of all bent functions with supports of size 2(t−1) + 2(t−2)/2 and the set of those with supports of size 2(t−1) −2(t−2)/2 are disjoint of same cardinality, the count of the bent functions in t variables for an even t is given by 2HFJh(s) where (v,k,λ) = ( 2t, 2(t−1) + 2(t−2)/2, 2(t−2) + 2(t−2)/2 ) . 3. A difference set criterion Theorem 2.1 imposes some restrictions on exchanges of elements of a (v,k1,λ1) difference set to get another (v,k2,λ2) difference set. By introducing a complex valued polynomial ∆(D1,D2)(X1, . . . ,Xt), we make these restrictions explicit, in terms of its certain values. Alternately, Theorem 2.1 can also be phrased in the language of group characters, following Theorem 11.18 on p. 224 of [8]. Let G = ∏t l=1 ( Z nlZ ) be an abelian group. For any il ∈ ZnlZ ; 0 ≤ l ≤ t, let i ∗ l ∈ {0, 1, . . . ,nl − 1} be such that il = i∗l + nlZ. 141 P. H. Keskar, P. Kumari / J. Algebra Comb. Discrete Appl. 8(2) (2021) 139–149 For any T ⊂ G, let ρG(T)(X1, . . . ,Xt) = ∑ (i1,...,it)∈T X i∗1 1 · · ·X i∗t t ∈ C[X1, . . . ,Xt]. Let U = {(ξ1, . . . ,ξt) ∈ Ct : ξnll = 1 for all 1 ≤ l ≤ t}. For any (ξ1, . . . ,ξt) ∈ U and (i1, . . . , it) ∈ G, we define ξi11 · · ·ξ it t = ξ i∗1 1 · · ·ξ i∗t t . Now let v = |G| and k,λ be non-negative integers. For any D ⊂ G, let D(−1) = {−d : d ∈ G}. In (3.2∗) of [5] it was proved that D is a (v,k,λ) difference set in G if and only if ρG(D)(ξ1, . . . ,ξt)ρG(D (−1))(ξ1, . . . ,ξt) −λρG(G)(ξ1, . . . ,ξt) − (k −λ) = 0 for all (ξ1, . . . ,ξt) ∈ U. Note that for any ξ ∈ C with |ξ| = 1, we have ξ−1 = ξ̄, the complex conjugate of ξ. It follows that ρG ( D(−1) ) (ξ1, . . . ,ξt) is the complex conjugate of ρG(D)(ξ1, . . . ,ξt) and hence we get D is a (v,k,λ) difference set in G if and only if |ρG(D)(ξ1, . . . ,ξt)|2 −λρG(G)(ξ1, . . . ,ξt) − (k −λ) = 0 for all (ξ1, . . . ,ξt) ∈ U. (1) Now let us assume ni = 2 for all i = 1, . . . , t then ρG(D)(ξ1, . . . ,ξt) ∈ R. Further ρG(G)(ξ1, . . . ,ξt) = 0 if ξi 6= 1 for some i ∈{1, . . . , t}, while ρG(D)(ξ1, . . . ,ξt) = k and ρG(G)(ξ1, . . . ,ξt) = v if ξi = 1 for all i ∈{1, . . . , t}. This has the following consequence : If ni = 2 for all i = 1, . . . , t then D is a (v,k,λ) difference set in G if and only if for any (ξ1, . . . ,ξt) ∈ U (ρG(D)(ξ1, . . . ,ξt)) = { k if ξi = 1 for all i ∈{1, . . . , t} ± √ k −λ otherwise. (2) Now suppose D1 is a (v,k1,λ1) difference set in G and D2 ⊂ G. Let ∆(D1,D2)(X1, . . . ,Xt) =ρG(D1 \D2)(X1, . . . ,Xt) −ρG(D2 \D1)(X1, . . . ,Xt). Then we have ∆(D1,D2)(X1, . . . ,Xt) = ρG(D1)(X1, . . . ,Xt) −ρG(D2)(X1, . . . ,Xt) and hence: If ni = 2 for all i = 1, . . . , t and D1 is a(v,k1,λ1) difference set in G then D2 is a (v,k2,λ2) difference set in G if and only if for any ξ = (ξ1, . . . ,ξt) ∈ U ∆(D1,D2)(ξ) ∈   {k1 −k2} if ξi = 1 for all i ∈{1, . . . , t}; { √ k1 −λ1 − √ k2 −λ2, √ k1 −λ1 + √ k2 −λ2} if ρG(D1)(ξ) = √ k1 −λ1; {− √ k1 −λ1 − √ k2 −λ2,− √ k1 −λ1 + √ k2 −λ2} if ρG(D1)(ξ) = − √ k1 −λ1. (3) 142 P. H. Keskar, P. Kumari / J. Algebra Comb. Discrete Appl. 8(2) (2021) 139–149 Moreover, if (v,k1,λ1) = (v,k2,λ2) then D2 is a (v,k1,λ1) difference set in G if and only if for any ξ = (ξ1, . . . ,ξt) ∈ U ∆(D1,D2)(ξ) ∈   {0} if ξi = 1 for all i ∈{1, . . . , t}; {0, 2 √ k1 −λ1} if ρG(D1)(ξ) = √ k1 −λ1; {−2 √ k1 −λ1, 0} if ρG(D1)(ξ) = − √ k1 −λ1. (4) 4. The analysis of C-condition In the rest of the paper, we continue with the notation and terminology introduced in Section 1. Moreover we identify Fr12 ×···× F ru 2 with F r1+···+ru 2 in a natural way. Also for any integer u ≥ 0, we denote by 0u the element of Fu2 whose all components are 0 and by 1u the element of F u 2 whose all components are 1. To search for examples when C-condition is not satisfied, we study the C-condition for (π,L). Since for any x ∈ F2, x2 = x, by reducing all the exponents of variables mod 2, without loss of generality we can assume P(X2, . . . ,Xm) = m−1∑ `=0 ∑ 2≤i1 s}|≥ 2 then C-condition is satisfied by (π,L). (C) Let L = {(0s,xs+1, . . . ,xm) : xi ∈ F2,s + 1 ≤ i ≤ m} be linear subspace of Fm2 . If αi1···i` = 1 for some (i1, . . . , i`) such that |{ij : ij > s}|≥ 2 then C-condition is not satisfied by (π,L). Moreover in (A) and (B), f(π,L) is a C-class bent function. Proof. The proof is based on the following observation : A nonempty subset F ⊂ Fm2 F is a flat ⇔ F − b is a subspace of Fm2 for some b ∈ F ⇔ F − b is a subspace of Fm2 for all b ∈ F. (5) We will apply this when F = π−1(a + L) and b = π−1(a) where a ∈ Fm2 . (A) For any a = (a1, . . . ,am) ∈ Fm2 we see that a + L = a∗ + L where a∗j = aj if j > s and a∗j = 0 otherwise. Thus we can assume, without loss of generality, that aj = 0 for j ≤ s. Therefore a + L = {(x1, . . . ,xs,as+1, . . . ,am) : x1, . . . ,xs ∈ F2}. It is enough to show that π−1(a + L) −π−1(a) is a subspace of Fm2 for all a = (0s,as+1, . . . ,am) ∈ Fm2 . 143 P. H. Keskar, P. Kumari / J. Algebra Comb. Discrete Appl. 8(2) (2021) 139–149 Clearly, π−1(a + L)−π−1(a) ⊂ L and they have same cardinality. Since |L| is finite, we get π−1(a + L)− π−1(a) = L. Thus π−1(a + L) −π−1(a) is a subspace for all a = (0s,as+1, . . . ,am) ∈ Fm2 . Hence (π,L) satisfies the C-condition. (B) For any a = (a1, . . . ,am) ∈ Fm2 we see that a + L = a∗ + L where a∗j = aj if j ≤ s and a∗j = 0 otherwise. Thus we can assume, without loss of generality, that aj = 0 for j > s. Therefore a + L = {(a1, . . . ,as,xs+1, . . . ,xm) : xs+1, . . . ,xm ∈ F2}. Consequently it is enough to show that π−1(a + L) −π−1(a) is a subspace of Fm2 for all a = (a1, . . . ,as,0m−s) ∈ Fm2 . For any (i1, . . . , i`), if αi1···i` = 1 then ∏ i∈{ij:ij≤s}ai is a constant in F2, and |{ij : ij > s}|≤ 1. So for any a = (a1, . . . ,as,0m−s) ∈ Fm2 , π−1(a + L) −π−1(a) = {(l(xs+1, . . . ,xm),0s−1,xs+1, . . . ,xm) : xs+1, . . . ,xm ∈ F2} where l(Xs+1, . . . ,Xm) ∈ F2[Xs+1, . . . ,Xm] is a polynomial of degree ≤ 1. Now for any u,v ∈ π−1(a + L) −π−1(a) and α,β ∈ F2, where u = (l(xs+1, . . . ,xm),0s−1,xs+1, . . . ,xm) and v = (l(x∗s+1, . . . ,x ∗ m),0s−1,x ∗ s+1, . . . ,x ∗ m), αu + βv = α(l(xs+1, . . . ,xm),0s−1,xs+1, . . . ,xm) + β(l(x ∗ s+1, . . . ,x ∗ m),0s−1,x ∗ s+1, . . . ,x ∗ m) = (αl(xs+1, . . . ,xm) + βl(x ∗ s+1, . . . ,x ∗ m),0s−1,αxs+1 + βx ∗ s+1, . . . ,αxm + βx ∗ m) Now π−1(a+0m)−π−1(a) = 0m. Therefore l(Xs+1, . . . ,Xm) is a polynomial with no constant term. Hence l(Xs+1, . . . ,Xm) is a linear transformation. Then αu + βv = (l(αxs+1 + βx ∗ s+1, . . . ,αxm + βx ∗ m),0s−1,αxs+1 + βx ∗ s+1, . . . ,αxm + βx ∗ m), therefore αu + βv ∈ π−1(a + L) −π−1(a). As a consequence, π−1(a + L) −π−1(a) is a subspace of Fm2 for all a = (a1, . . . ,as,0m−s) ∈ Fm2 and hence (π,L) satisfy C-condition. (C) We classify nonzero terms of P(X2, . . . ,Xm) in two types. Type 1 : corresponding to (i1, . . . , i`) such that |{ij : ij > s}|≥ 2, Type 2 : corresponding to (i1, . . . , i`) such that |{ij : ij > s}| < 2. Let T1 = Xi∗1 · · ·Xi∗`∗ be minimal among all nonzero terms of P(X2, . . . ,Xm) of Type 1 with the divisibility partial order. Hence for every nonzero term T 6= T1 of Type 1 of P(X2, . . . ,Xm) corresponding to (i1, . . . , i`) , there exists 1 ≤ j ≤ ` such that ij 6∈ {i∗1, . . . , i∗`∗}, and therefore T is divisible by Xij. For any a = (a1, . . . ,am) ∈ Fm2 we see that a + L = a∗ + L where a∗j = aj if j ≤ s and a ∗ j = 0 otherwise. Thus we can assume, without loss, that aj = 0 for j > s. Therefore a + L = {(a1, . . . ,as,xs+1, . . . ,xm) : xs+1, . . . ,xm ∈ F2}. In view of (5), we want to show that π−1(a + L) −π−1(a) is not a subspace of Fm2 for some a = (a1, . . . ,as,0m−s) ∈ Fm2 . Let aj = 1 for all j = i∗u ≤ s and aj = 0 for any j ∈ {1, 2, . . . ,s}\{i∗1, . . . , i∗`∗}. Since any term of P(X2, . . . ,Xm) of Type 1 except T1 is divisible by Xij for some ij 6∈ {i∗1, . . . , i∗`∗}, in addition if we let xj = 0 for all j ∈{s + 1, . . . ,m}\{i∗1, . . . , i∗`∗} then π−1(a1, . . . ,as,xs+1, . . . ,xm) = (( a1 + l(xs+1, . . . ,xm) + `∗∏ r=s0 xi∗r ) ,a2, . . . ,as,xs+1, . . . ,xm ) 144 P. H. Keskar, P. Kumari / J. Algebra Comb. Discrete Appl. 8(2) (2021) 139–149 where s0 = min{j ∈{1, . . . ,`∗} : i∗j > s} and l(Xs+1, . . . ,Xm) is a polynomial of degree ≤ 1 coming from terms of Type 2. Therefore, in this case, π−1(a + L) −π−1(a) = {(( l(xs+1, . . . ,xm) − l(0m−s) + `∗∏ r=s0 xi∗r ) ,0s−1,xs+1, . . . ,xm ) : xs+1, . . . ,xm ∈ F2 } . For s0 ≤ j ≤ `∗, let ei∗ j = (xs+1, . . . ,xm) be such that xi∗ j = 1 and xi = 0 for i 6= i∗j and let fi∗ j = π−1(a + (0s,ei∗ j )) − π−1(a). Then fi∗ j = ( l(ei∗ j ) − l(0m−s),0s−1,ei∗ j ) , as xi∗u = 0 for u 6= j. Now fi∗ j ∈ π−1(a + L) − π−1(a) for all s0 ≤ j ≤ `∗. On the other hand, ∑`∗ j=s0 fi∗ j =( l( ∑`∗ j=s0 ei∗ j ) − l(0m−s),0s−1, ∑`∗ j=s0 ei∗ j ) , as l(Xs+1, . . . ,Xm) − l(0m−s) is a homogeneous linear poly- nomial. Denoting ∑`∗ j=s0 ei∗ j by (ys+1, . . . ,ym), we have ∑`∗ j=s0 fi∗ j = (y1,0s−1,ys+1, . . . ,ym) where y1 = l(ys+1, . . . ,ym) − l(0m−s). Since ∏`∗ r=s0 yi∗r = 1, we see that ∑`∗ j=s0 fi∗ j 6∈ π−1(a + L) −π−1(a). As a consequence, π−1(a + L) − π−1(a) is not a subspace of Fm2 and hence (π,L) does not satisfy C-condition. 5. Non-bentness of an infinite family The violation of C-condition by (π,L) is not sufficient to show f(π,L) is not bent. Using the adaptation of difference set criterion from Section 3, we will show the non-bentness of f(π,L) for several (π,L) in every even dimension. We require the following Lemma 5.1. Let m ≥ 3 and 1 ≤ s ≤ m− 2 be integers. Then∑ (xs+1,...,xm)∈Fm−s2 (−1)( ∑m i=s+1 xi+ ∏m i=s+1(xi+1)) = −2. Proof. More generally, we will prove : for any j = s,s + 1, · · · ,m− 1,∑ (xj+1,...,xm)∈F m−j 2 (−1)( ∑m i=j+1 xi+ ∏m i=j+1(xi+1)) = −2. (†) We prove (†) by induction on u = m− j. If u = 1, we have j = m− 1. Since∑ xm∈F2 (−1)(1+(xm+1))(−1)xm = 2, (†) holds for u = 1. Assume (†) for u = ν where ν ≤ m− 2 and let u = ν + 1, that is, j = m−ν − 1. Now ∑ (xj+1,...,xm)∈F m−j 2 (−1)( ∑m i=j+1 xi+ ∏m i=j+1 (xi+1)) = ∑ (xm−ν,...,xm)∈Fν+12 (−1)( ∑m i=m−ν xi+ ∏m i=m−ν(xi+1)) = − ∑ (xm−ν,...,xm)∈Fν+12 ( (−1)(1+ ∏m i=m−(ν−1)(xi+1)) )(xm−ν+1) (−1)( ∑m i=m−(ν−1) xi) 145 P. H. Keskar, P. Kumari / J. Algebra Comb. Discrete Appl. 8(2) (2021) 139–149 = − ∑ (x(m−ν)+1,...,xm)∈Fν2 (−1)(1+ ∏m i=(m−ν)+1(xi+1))(−1)( ∑m i=(m−ν)+1 xi) − ∑ (x(m−ν)+1,...,xm)∈Fν2 (−1)( ∑m i=(m−ν)+1 xi) Since ∑ xm∈F2 (−1) xm = 0, ∑ (x(m−ν)+1,...,xm)∈Fν2 (−1)( ∑m i=(m−ν)+1) xi) = m∏ i=(m−ν)+1 ( ∑ xi∈F2 (−1)xi ) = 0. Moreover as (†) holds for u = ν, that is j = m−ν, we have∑ (x(m−ν)+1,...,xm)∈Fν2 (−1)( ∏m i=(m−ν)(xi+1))(−1)( ∑m i=(m−ν)+1 xi) = −2. As a consequence, (†) holds for u = ν + 1. This completes the proof. Now we come to the main result. Theorem 5.2. Let m ≥ 3 and 1 ≤ r ≤ s ≤ m − 2 be integers. Further let L = {(0s,xs+1, . . . ,xm) : xi ∈ F2,s + 1 ≤ i ≤ m} be an m − s dimensional linear subspace of Fm2 and π(x) =( (x1 + ∏m i=r+1 xi),x2, . . . ,xm ) be a permutation of Fm2 . Then f(π,L) : F 2m 2 → F2 is not a bent func- tion. Proof. Since L = {(0s,xs+1, . . . ,xm) : xi ∈ F2,s + 1 ≤ i ≤ m} we have L⊥ = {(x1, . . . ,xs,0m−s) : xi ∈ F2, 1 ≤ i ≤ s}. Also for any y = (y1, . . . ,ym) ∈ Fm2 , π−1(y) = (( y1 + ∏m i=r+1 yi ) ,y2, . . . ,ym ) . Therefore f(π,L)(x,y) = m∑ i=1 xiyi + x1 m∏ i=r+1 yi + m∏ i=s+1 (xi + 1) = f(x,y) + x1 m∏ i=r+1 yi where f(x,y) = ∑m i=1 xiyi + ∏m i=s+1(xi + 1) is a M-class bent function in 2m variables, see p. 90 of [4]. Let D(π,L) and D denote the supports of f(π,L) and f respectively.Then D \D(π,L) = {(x,y) ∈ D : x1 m∏ i=r+1 yi = 1}. We know x1 m∏ i=r+1 yi = 1 ⇐⇒ x1 = yr+1 = · · · = ym = 1. Therefore (x,y) ∈ D and x1 m∏ i=r+1 yi = 1 ⇐⇒ y1 + r∑ i=2 xiyi + m∑ i=r+1 xi + m∏ i=s+1 (xi + 1) = 1 and 146 P. H. Keskar, P. Kumari / J. Algebra Comb. Discrete Appl. 8(2) (2021) 139–149 x1 = yr+1 = · · · = ym = 1 ⇐⇒ y1 = 1 + r∑ i=2 xiyi + m∑ i=r+1 xi + m∏ i=s+1 (xi + 1) and x1 = yr+1 = · · · = ym = 1. Consequently D \D(π,L) = {(1,x2, . . . ,xm, 1 + r∑ i=2 xiyi + m∑ i=r+1 xi + m∏ i=s+1 (xi + 1),y2, . . . ,yr,1m−r) : x2, . . . ,xm,y2, . . . ,yr ∈ F2} and hence |D \D(π,L)| = 2m+r−2. Now, if D̄ denotes the complement of D in F2m2 , D(π,L) \D = {(x,y) ∈ D̄ : x1 m∏ i=r+1 yi = 1} = {(1,x2, . . . ,xm, r∑ i=2 xiyi + m∑ i=r+1 xi + m∏ i=s+1 (xi + 1),y2, . . . ,yr,1m−r) : x2, . . . ,xm,y2, . . . ,yr ∈ F2} and hence |D(π,L) \D| = 2m+r−2. Let U = {1,−1}2m. Then for any (ξ,η) ∈ U we have ∆(D,D(π,L))(ξ,η) = ξ1ηr+1 · · ·ηm(η1 − 1)×∑ (x2,...,xm,y2,...,yr)∈Fm+r−22 ξx22 · · ·ξ xm m η ( ∑r i=2 xiyi+ ∑m i=r+1 xi+ ∏m i=s+1 (xi+1)) 1 η y2 2 · · ·η yr r . Henceforth let ξ1 = · · · = ξr = 1,ξr+1 = · · · = ξs = −1,ξs+1 = · · · = ξm = 1,η1 = −1,η2 = · · · = ηm = 1. Further let Λ1 = ∑ (x2,...,xr,y2,...,yr)∈F2r−22 (−1)( ∑r i=2 xiyi) and Λ2 = ∑ (xs+1,...,xm)∈Fm−s2 (−1)( ∑m i=s+1 xi+ ∏m i=s+1 (xi+1)). Then ∆(D,D(π,L))(ξ,η) = −2 ∑ (xr+1,...,xs)∈Fs−r2 (Λ1Λ2) = −2s−r+1 (Λ1Λ2) . 147 P. H. Keskar, P. Kumari / J. Algebra Comb. Discrete Appl. 8(2) (2021) 139–149 Now Λ1 = (∑ (x2,y2)∈F22 (−1)x2y2 ) · · · (∑ (xr,yr)∈F22 (−1)xryr ) and∑ (xi,yi)∈F22 (−1)xiyi = 2 for any i = 2, . . . ,r. Hence by Lemma 5.1, ∆(D,D(π,L))(ξ,η) = −2sΛ2 = 2s+1. Since |D \D(π,L)| = |D(π,L) \D| = 2m−1, we have |D| = |D(π,L)|. If f(π,L) is a bent function, then D(π,L) is a difference set. Thus by Ryser’s condition (see Section 3 of [5]), it follows that parameters (v,k,λ) of D(π,L) are same as those of D, hence k−λ = 2t−2 = 22(m−1). Consequently, by (4) of Section 3, for any (ξ,η) ∈ U, ∆(D,D(π,L)) ∈{0,±2 √ (k −λ)} = {0,±2m}. But we have found (ξ,η) ∈ U such that ∆(D,D(π,L)) = 2s+1 6∈ {0,±2m} for any 1 ≤ s ≤ m − 2. Therefore f(π,L) is not bent function. Remark 5.3. The alternate tools for proving the non-bentness of f(π,L) could have been Theorem on p. 94 of [2] or Proposition 1 on p. 398 of [6]. As far as [2] is concerned, checking the required conditions is tedious. On the other hand, to prove non-bentness of f(π,L) using [6],it is sufficient to have either (a) the Hamming distance d(f,f(π,L)) < 2m or (b) d(f,f(π,L)) = 2m and either support A of f + f(π,L) is not a flat or the restriction of f to A is not an affine function. Now d ( f,f(π,L) ) = |D\D(π,L)|+|D(π,L)\D| = 2m+r−1. So if r > 1 then Proposition 1 of [6] doesn’t help, though it suffices for r = 1. 6. Computational results In this section, we report some more (π,L) such that f(π,L) is not bent. This was established through implementations of methods of previous sections as well as [5] using programs in C++ language. In Section 5, the polynomial P(X2, · · · ,Xm) contained only one term of Type 1 (as described in case (C) of Theorem 4.1). Examples 6.1 and 6.2 contain more than one term of Type 1. Example 6.1. Let L = {(0, 0,x3,x4) : x3,x4 ∈ F2} be a linear subspace of F42 and π(x) = (x1 + αx2x3 + βx2x4 + γx3x4 + δx2x3x4,x2,x3,x4) : α,β,γ,δ ∈ F2 be a permutation of F42. Then f(π,L) : F42 ×F42 → F2 is a C-class bent function when γ = δ = 0 and f(π,L) is not a bent function otherwise. Let us provide some justification for this. Clearly when γ = δ = 0, then by (B) of Theorem 4.1, (π,L) satisfies C-condition. Let D(π,L) denote the support of f(π,L). When γ = 1, for ξ = (1, 1, 1, 1,−1, 1, 1, 1) ∈ U, we see that ( ρG(D(π,L))(ξ) )2 −λρG(G)(ξ) − (k −λ) = −64 6= 0. When (γ,δ) = (0, 1), (α,β) 6= (1, 1), for ξ = (1,−1, 1, 1,−1, 1, 1, 1) we have ( ρG(D(π,L))(ξ) )2 −λρG(G)(ξ)−(k−λ) = −64 6= 0. Further when α,β,γ,δ) = (1, 1, 0, 1), for ξ = (1,−1, 1, 1,−1, 1, 1, 1) we have ( ρG(D(π,L))(ξ) )2 −λρG(G)(ξ) − (k−λ) = 192 6= 0. When α = β = γ = 0 and δ = 1, we get a special case of the family in Section 5. Using Matlab, we have also determined that its Walsh-Hadamard spectrum (see [7]) contains -16 with multiplicity 104, 16 with multiplicity 88, each of -32 and 32 with multiplicity 8 and 0 with multiplicity 48. It has also been verified that in the other non-bentness cases of Example 6.1, Walsh-Hadamard spectrum is not contained in {±2m}. This provides another verification of non-bentness, following the definition in [7]. Example 6.2. Let L = {(0, 0,x3,x4,x5,x6) : x3,x4,x5,x6 ∈ F2} be a linear subspace of F62 and π(x) = (x1 + x3x4 + x5x6,x2,x3,x4,x5,x6) be a permutation of F62. Then f(π,L) : F 6 2 × F62 → F2 is not a bent function. This can be justified by observing that ( ρG(D(π,L))(ξ) )2 −λρG(G)(ξ) − (k −λ) = −768 6= 0 where D(π,L) is the support of f(π,L) and ξ = (1, 1, 1, 1, 1, 1,−1, 1, 1, 1, 1, 1) ∈ U. 148 P. H. Keskar, P. Kumari / J. Algebra Comb. Discrete Appl. 8(2) (2021) 139–149 7. Concluding remarks In this paper, we have connected the count of abelian difference sets with given parameters to computation of Hilbert functions of an ideal. There are algorithms for computation of Hilbert function. While diffculties in implementation for large values of parameters need to be addressed, the theoretical consequences of this connection can also be explored. We also undertook to explore bentness of f(π,L) when (π,L) does not satisfy C-condition. Theorem 4.1 (C) helped us determine the choice of (π,L) for exploration and Sections 5 and 6 provided the results of exploration.This work was prompted by the following questions which still await the answers. Question 1. Is C-condition necessary for bentness of f(π,L)? If yes, then provide the proof or else provide the counter-example. Question 2. As a consequence of Theorem 4.1 (B) and (C), it follows that if L = {(0s,xs+1, . . . ,xm) : xi ∈ F2,s + 1 ≤ i ≤ m} and πi(x1, . . . ,xm) = (x1 + Pi(x2, . . . ,mm),x2, . . . ,xm) for i = 1, 2 are such that (πi,L) satisfies C-condition for i = 1, 2 then (π1 ◦π2,L) also satisfies C-condition. What can we say about bentness of f(π1◦π2,L) if we know bentness of f(πi,L) for i = 1, 2? In general, for a given subspace L of Fm2 , is there a semigroup structure on the set of all permutations π of F m 2 such that f(π,L) is bent? If not, what are the counterexamples? We hope to continue our exploration further guided by these questions. Acknowledgment: Both the authors thank the support from FIST Programme vide SR/FST/MSI- 090/2013 of DST, Govt. of India. The second author thanks UGC, Govt of India for the support under SRF Programme (SR. No. 2061540979, Ref. No. 21/06/2015(1)EU-V R. No. 426800). References [1] T. Becker, V. Weispfennig, Groebner bases a computational approach to commutative algebra, Springer (1993). [2] C. Carlet, Two new classes of bent functions, Advances in Cryptology-EUROCRYPT’93, LNCS vol 765 (Ed. T. Hellseth) Springer-Verlag (1994) 77–101. [3] D. Cox, J. Little, D. O’Shea, Ideals, varieties and algorithms, Springer Verlag, New York Inc (2007). [4] J. F. Dillon, Elementary hadamard difference sets, Ph. D. Thesis, University of Maryland (1974). [5] P. H. Keskar, P. Kumari, Polynomial criterion for abelian difference sets, Indian Journal of Pure and Applied Mathematics 51(1) (2020) 233–249. [6] N. Kolomeec, The graph of minimal distances of bent functions and its properties, Designs, Codes and Cryptography 85 (2017) 395–410. [7] B. Mandal, P. Stănică, S. Gangopadhyay, E. Pasalic, An analysis of the C class of bent functions, Fundamenta Informaticae 146(3) (2016) 271–292. [8] E. H. Moore, H. S. Pollatsek, Difference sets, connecting algebra, combinatorics, and geometry, american mathematical society (2013). [9] N.Tokareva, Bent functions: Results and applications to cryptography, Elsevier (2015). [10] A. van den Essen, Polynomial automorphisms and the jacobian conjecture, Birkhauser (2000). 149 https://doi.org/10.1007/3-540-48285-7_8 https://doi.org/10.1007/3-540-48285-7_8 https://doi.org/10.1007/s13226-020-0397-5 https://doi.org/10.1007/s13226-020-0397-5 https://doi.org/10.1007/s10623-016-0306-4 https://doi.org/10.1007/s10623-016-0306-4 https://doi.org/10.3233/FI-2016-1386 https://doi.org/10.3233/FI-2016-1386 Introduction Counting the difference sets A difference set criterion The analysis of C-condition Non-bentness of an infinite family Computational results Concluding remarks References