Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions

We survey the properties of two parameters introduced by C. Ding and the author for quantifying the balancedness of vectorial functions and of their derivatives. We give new results on the distribution of the values of the first parameter when applied to F + L, where F is a fixed function and L ranges over the set of linear functions: we show an upper bound on the nonlinearity of F by means of these values, we determine then the mean of these values and we show that their maximum is a nonlinearity parameter as well, we prove that the variance of these values is directly related to the second parameter. We briefly recall the known constructions of bent vectorial functions and introduce two new classes obtained with Gregor Leander. We show that bent functions can be used to build APN functions by concatenating the outputs of a bent (n, n/2)-function and of some other (n, n/2)-function. We obtain this way a general infinite class of quadratic APN functions. We show that this class contains the APN trinomials and hexanomials introduced in 2008 by L. Budaghyan and the author, and a class of APN functions introduced, in 2008 also, by Bracken et al.; this gives an explanation of the APNness of these functions and allows generalizing them. We also obtain this way the recently found Edel?CPott cubic function. We exhibit a large number of other sub-classes of APN functions. We eventually design with this same method classes of quadratic and non-quadratic differentially 4-uniform functions.     

A new family of differentially 4-uniform permutations over $$\mathbb{F}_{2^{2k} }$$ for odd k

We study the differential uniformity of a class of permutations over \(\mathbb{F}_{2^n } \) with n even. These permutations are different from the inverse function as the values x^?1 are modified to be (γx)^? on some cosets of a fixed subgroup 〈γ〉 of \(\mathbb{F}_{2^n }^* \). We obtain some sufficient conditions for this kind of permutations to be differentially 4-uniform, which enable us to construct a new family of differentially 4-uniform permutations that contains many new Carlet-Charpin-Zinoviev equivalent (CCZ-equivalent) classes as checked by Magma for small numbers n. Moreover, all of the newly constructed functions are proved to possess optimal algebraic degree and relatively high nonlinearity.     

Bundles, presemifields and nonlinear functions

Bundles are equivalence classes of functions derived from equivalence classes of transversals. They preserve measures of resistance to differential and linear cryptanalysis. For functions over GF(2 ⁿ ), affine bundles coincide with EA-equivalence classes. From equivalence classes (“bundles”) of presemifields of order p ⁿ , we derive bundles of functions over GF(p ⁿ ) of the form λ(x)*ρ(x), where λ, ρ are linearised permutation polynomials and * is a presemifield multiplication. We prove there are exactly p bundles of presemifields of order p ² and give a representative of each. We compute all bundles of presemifields of orders p ⁿ ≤ 27 and in the isotopism class of GF(32) and we measure the differential uniformity of the derived λ(x)*ρ(x). This technique produces functions with low differential uniformity, including PN functions (p odd), and quadratic APN and differentially 4-uniform functions (p = 2).     

Association schemes arising from bent functions

We give a construction of 3-class and 4-class association schemes from s-nonlinear and differentially 2 ^s -uniform functions, and a construction of p-class association schemes from weakly regular p-ary bent functions, where p is an odd prime.     

A negative answer to Bracken–Tan–Tan's problem on differentially 4-uniform permutations over F2n

Permutations with low differential uniformity are widely used in cipher design. Recently, Bracken, Tan and Tan (2012) [5] presented a method to construct differentially 4-uniform permutations by changing certain conditions of known APN functions. They guessed that only two classes of existing quadratic APN functions have this property. They succeeded in proving one class and left the other one as an open problem. In this paper, with the help of a computer, those polynomials are proved to be differentially 4-uniform but may not be permutation polynomials, which give a negative answer to this problem.     

Constructing differentially 4-uniform permutations over GF(22m ) from quadratic APN permutations over GF(22m+1)

In this paper, by means of the idea proposed by Carlet (ACISP 1-15, 2011), differentially 4-uniform permutations with the best known nonlinearity over \({\mathbb{F}_{2^{2m}}}\) are constructed using quadratic APN permutations over \({\mathbb{F}_{2^{2m+1}}}\) . Special constructions are given using the Gold functions. The algebraic degree of the constructions and their compositional inverses is also investigated. One construction and its compositional inverse both have algebraic degree m + 1 over \({\mathbb{F}_2^{2m}}\) .     

3-uniform hypergraphs avoiding a given odd cycle

We give upper bounds for the size of 3-uniform hypergraphs avoiding a given odd cycle using the definition of a cycle due to Berge. In particular, we show that a 3-uniform hypergraph containing no cycle of length 2k+1 has less than 4k ⁴ n ^1+1/k +O(n) edges. Constructions show that these bounds are best possible (up to constant factor) for k=1,2,3, 5.     

On the symmetric properties of APN functions

We study the symmetric properties of APN functions as well as the structure and properties of the range of an arbitrary APN function. We prove that there is no permutation of variables that preserves the values of an APN function. Upper bounds for the number of symmetric coordinate Boolean functions in an APN function and its coordinate functions invariant under a cyclic shift are obtained. For n ≤ 6, some upper bounds for the maximal number of identical values of an APN function are given and a lower bound is found for different values of an arbitrary APN function of n variables.     

Hypergeometric series well-poised in SU(n) and a generalization of Biedenharn's G-functions

We prove that Holman's hypergeometric series well-poised in SU(n) satisfy a general difference equation. We make use of the “path sum” function developed by Biedenharn and this equation to show that a special class of these series, multiplied by simple products, may be regarded as a U(n) generalization of Biedenharn and Louck's G(Δ; X) functions for U(3). The fact that these generalized G-functions are polynomials follows from a detailed study of their symmetries and zeros. As a further application of our general difference equations, we give an elementary proof of Holman's U(n) generalization of the ₅F₄(1) summation theorem.     

Characterization of TL-uniform spaces by coverings

In this paper we introduce the concepts of fuzzy TL-uniform spaces by means of coverings, where T stands for any continuous triangular norm. We show that the structure of covering TL-uniform spaces are isomorphic to fuzzy TL-uniform spaces as defined by Hashem and Morsi (2006) [4]. In particular, we study the continuity of functions between covering TL-uniform spaces, the I-topological space associated with a covering TL-uniform space. Also, we define the notions of level covering uniformities for a covering TL-uniformity. Moreover, we deduce a number of functors between categories of covering TL-uniform spaces, fuzzy TL-uniform spaces, covering uniform spaces and uniform spaces.     

The smallestn-uniform hypergraph with positive discrepancy

A two-coloring of the verticesX of the hypergraphH=(X, ε) by red and blue hasdiscrepancy d ifd is the largest difference between the number of red and blue points in any edge. A two-coloring is an equipartition ofH if it has discrepancy 0, i.e., every edge is exactly half red and half blue. Letf(n) be the fewest number of edges in ann-uniform hypergraph (all edges have sizen) having positive discrepancy. Erd?s and Sós asked: isf(n) unbounded? We answer this question in the affirmative and show that there exist constantsc ₁ andc ₂ such that $$\frac{{c_1 \log (snd(n/2))}}{{\log \log (snd(n/2))}} \leqq f(n) \leqq c_2 \frac{{\log ^3 (snd(n/2))}}{{\log \log (snd(n/2))}}$$ where snd(x) is the least positive integer that does not dividex.     

Disproof of the neighborhood conjecture with implications to SAT

We study a special class of binary trees. Our results have implications on Maker/Breaker games and SAT: We disprove a conjecture of Beck on positional games and construct an unsatisfiable k-CNF formula with few occurrences per variable, thereby improving a previous result by Hoory and Szeider and showing that the bound obtained from the Lovász Local Lemma is tight up to a constant factor. A (k, s)-CNF formula is a boolean formula in conjunctive normal form where every clause contains exactly k distinct literals and every variable occurs in at most s clauses. The (k, s)-SAT problem is the satisfiability problem restricted to (k, s)-CNF formulas. Kratochvíl, Savický and Tuza showed that for every k≥3 there is an integer f(k) such that every (k, f(k))-CNF formula is satisfiable, but (k, f(k) + 1)-SAT is already NP-complete (it is not known whether f(k) is computable). Kratochvíl, Savický and Tuza also gave the best known lower bound $f(k) = \Omega \left( {\tfrac{{2^k }} {k}} \right)$ , which is a consequence of the Lovász Local Lemma. We prove that, in fact, $f(k) = \Theta \left( {\tfrac{{2^k }} {k}} \right)$ , improving upon the best known upper bound $O\left( {(\log k) \cdot \tfrac{{2^k }} {k}} \right)$ by Hoory and Szeider. Finally we establish a connection between the class of trees we consider and a certain family of positional games. The Maker/Breaker game we study is as follows. Maker and Breaker take turns in choosing vertices from a given n-uniform hypergraph $\mathcal{F}$ , with Maker going first. Maker’s goal is to completely occupy a hyperedge and Breaker tries to prevent this. The maximum neighborhood size of a hypergraph $\mathcal{F}$ is the maximal s such that some hyperedge of $\mathcal{F}$ intersects exactly s other hyperedges. Beck conjectures that if the maximum neighborhood size of $\mathcal{F}$ is smaller than 2 ^n?1 ? 1 then Breaker has a winning strategy. We disprove this conjecture by establishing, for every n≥3, the existence of an n-uniform hypergraph with maximum neighborhood size 3·2 ^n?3 where Maker has a winning strategy. Moreover, we show how to construct, for every n, an n-uniform hypergraph with maximum degree at most $\frac{{2^{n + 2} }} {n}$ where Maker has a winning strategy. In addition we show that each n-uniform hypergraph with maximum degree at most $\frac{{2^{n - 2} }} {{en}}$ has a proper halving 2-coloring, which solves another open problem posed by Beck related to the Neighborhood Conjecture.     

Representations of the Strong Endomorphism Monoid of Finite n-Uniform Hypergraphs

In this paper, two exact representations of the strong endomorphism monoid of an arbitrary finite n-uniform hypergraph are described. It is proved that the strong endomorphism monoid of a finite n-uniform hypergraph is regular. We find all nonnegative integers n such that n-uniform hypergraphs are determined by their strong endomorphisms.     

Monochromatic Matchings in the Shadow Graph of Almost Complete Hypergraphs

Edge colorings of r-uniform hypergraphs naturally define a multicoloring on the 2-shadow, i.e., on the pairs that are covered by hyperedges. We show that in any (r – 1)-coloring of the edges of an r-uniform hypergraph with n vertices and at least (1-e)( *20c nr)(1-\varepsilon)\left( {\begin{array}{*{20}c} n\\ r\\ \end{array}}\right) edges, the 2-shadow has a monochromatic matching covering all but at most o(n) vertices. This result confirms an earlier conjecture and implies that for any fixed r and sufficiently large n, there is a monochromatic Berge-cycle of length (1 – o(1))n in every (r – 1)-coloring of the edges of K^(r)_n{K^{(r)}_{n}}, the complete r-uniform hypergraph on n vertices.     

Some results concerning cryptographically significant mappings over GF(2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)

In this paper we investigate the existence of permutation polynomials of the form F(x) = x ^d  + L(x) over GF(2 ⁿ ), L being a linear polynomial. The results we derive have a certain impact on the long-term open problem on the nonexistence of APN permutations over GF(2 ⁿ ), when n is even. It is shown that certain choices of exponent d cannot yield APN permutations for even n. When n is odd, an infinite class of APN permutations may be derived from Gold mapping x ³ in a recursive manner, that is starting with a specific APN permutation on GF(2 ^k ), k odd, APN permutations are derived over GF(2 ^k+2i ) for any i ≥ 1. But it is demonstrated that these classes of functions are simply affine permutations of the inverse coset of the Gold mapping x ³. This essentially excludes the possibility of deriving new EA-inequivalent classes of APN functions by applying the method of Berveglieri et al. (approach proposed at Asiacrypt 2004, see [3]) to arbitrary APN functions.     

Exact solution of the hypergraph Turán problem for k-uniform linear paths

A k-uniform linear path of length ?, denoted by ? _? ^(k) , is a family of k-sets {F ₁,...,F _? such that |F _i ∩ F _i+1|=1 for each i and F _i ∩ F _bj = \(\not 0\) whenever |i?j|>1. Given a k-uniform hypergraph H and a positive integer n, the k-uniform hypergraph Turán number of H, denoted by ex _k (n, H), is the maximum number of edges in a k-uniform hypergraph \(\mathcal{F}\) on n vertices that does not contain H as a subhypergraph. With an intensive use of the delta-system method, we determine ex _k (n, P _? ^(k) exactly for all fixed ? ≥1, k≥4, and sufficiently large n. We show that $ex_k (n,\mathbb{P}_{2t + 1}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} )$ . The only extremal family consists of all the k-sets in [n] that meet some fixed set of t vertices. We also show that $ex(n,\mathbb{P}_{2t + 2}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} ) + (_{k - 2}^{n - t - 2} )$ , and describe the unique extremal family. Stability results on these bounds and some related results are also established.     

On Ramsey—Turán type theorems for hypergraphs

LetH ^r be anr-uniform hypergraph. Letg=g(n;H ^r ) be the minimal integer so that anyr-uniform hypergraph onn vertices and more thang edges contains a subgraph isomorphic toH ^r . Lete =f(n;H ^r ,εn) denote the minimal integer such that everyr-uniform hypergraph onn vertices with more thane edges and with no independent set ofεn vertices contains a subgraph isomorphic toH ^r . We show that ifr>2 andH ^r is e.g. a complete graph then $$\mathop {\lim }\limits_{\varepsilon \to 0} \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} f(n;H^r ,\varepsilon n) = \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} g(n;H^r )$$ while for someH ^r with \(\mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} g(n;H^r ) \ne 0\) $$\mathop {\lim }\limits_{\varepsilon \to 0} \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} f(n;H^r ,\varepsilon n) = 0$$ . This is in strong contrast with the situation in caser=2. Some other theorems and many unsolved problems are stated.     

On Turan hypergraphs

Let α(H) be the stability number of a hypergraph H = (X, $\text{E}$). T(n, k, α) is the smallest q such that there exists a k-uniform hypergraph H with n vertices, q edges and with α(H) ? α. A k-uniform hypergraph H, with n vertices, T(n, k, α) edges and α(H) ?α is a Turan hypergraph. The value of T(n, 2, α) is given by a theorem of Turan. In this paper new lower bounds to T(n, k, α) are obtained and it is proved that an infinity of affine spaces are Turan hypergraphs.     

Polynomial behavior of special values of partial zeta functions of real quadratic fields at s = 0

We compute the special values of partial zeta functions at s = 0 for family of real quadratic fields K _n and ray class ideals ${\mathfrak{b}_n}$ such that ${\mathfrak{b}_n^{-1} = [1, \delta(n)]}$ where the continued fraction expansion of δ(n) ? 1 is purely periodic and terms are polynomials in n of degree bounded by d. With additional assumptions, we prove that the special values of the partial zeta functions at s = 0 are given by a quasi-polynomial of degree less than or equal to d as a function of n. We apply this to conclude that the special values of the Hecke’s L-functions at s = 0 for the family ${(K_n, \mathfrak{b}_n, \chi_n:= \chi \circ N_{K_n/\mathbb{Q}})}$ for any Dirichlet character χ behave like quasi-polynomial as well. We compute explicitly the coefficients of the quasi-polynomials. Two examples satisfying the condition are presented, and for these two families, the special values of the partial zeta functions at s = 0 are given.     

Counting substructures II: Hypergraphs

For various k-uniform hypergraphs F, we give tight lower bounds on the number of copies of F in a k-uniform hypergraph with a prescribed number of vertices and edges. These are the first such results for hypergraphs, and extend earlier theorems of various authors who proved that there is one copy of F. A sample result is the following: Füredi-Simonovits [11] and independently Keevash-Sudakov [16] settled an old conjecture of Sós [29] by proving that the maximum number of triples in an n vertex triple system (for n sufficiently large) that contains no copy of the Fano plane is p(n)=( ₂ ^?n/2? )?n/2?+( ₂ ^?n/2? ?n/2?). We prove that there is an absolute constant c such that if n is sufficiently large and 1 ≤ q ≤ cn ², then every n vertex triple system with p(n)+q edges contains at least $6q\left( {\left( {_4^{\left\lfloor {n/2} \right\rfloor } } \right) + \left( {\left\lceil {n/2} \right\rceil - 3} \right)\left( {_3^{\left\lfloor {n/2} \right\rfloor } } \right)} \right)$ copies of the Fano plane. This is sharp for q≤n/2–2. Our proofs use the recently proved hypergraph removal lemma and stability results for the corresponding Turán problem.