Gowers $$U_3$$ norm of some classes of bent Boolean functions

The Gowers \(U_3\) norm of a Boolean function is a measure of its resistance to quadratic approximations. It is known that smaller the Gowers \(U_3\) norm for a Boolean function larger is its resistance to quadratic approximations. Here, we compute Gowers \(U_3\) norms for some classes of Maiorana–McFarland bent functions. In particular, we explicitly determine the value of the Gowers \(U_3\) norm of Maiorana–McFarland bent functions obtained by using APN permutations. We prove that this value is always smaller than the Gowers \(U_3\) norms of Maiorana–McFarland bent functions obtained by using differentially \(\delta \)-uniform permutations, for all \(\delta \ge 4\). We also compute the Gowers \(U_3\) norms for a class of cubic monomial functions, not necessarily bent, and show that for \(n=6\), these norm values are less than that of Maiorana–McFarland bent functions. Further, we computationally show that there exist 6-variable functions in this class which are not bent but achieve the maximum second-order nonlinearity for 6 variables.     

Gowers norms and pseudorandom measures of subsets

Let $A \subset {{\Bbb Z}_N}$, and ${f_A}(s) = \left\{ {\begin{array}{*{20}{l}}{1 - \frac{{|A|}}{N},}&{{\rm{for}}\;s \in A,}\\{ - \frac{{|A|}}{N},}&{{\rm{for}}\;s \notin A.}\end{array}} \right.$ We define the pseudorandom measure of order k of the subset A as follows, P_k(A, N) = $\begin{array}{*{20}{c}}{\max }\\D\end{array}$|$\mathop \Sigma \limits_{n \in {\mathbb{Z}_N}}$f_A(n + c₁)f_A(n + c₂) … f_A(n + c_k)|, where the maximum is taken over all D = (c₁, c₂, . . . , c_k) ∈ ${\mathbb{Z}^k}$ with 0 ≤ c₁ < c₂ < … < c_k ≤ N - 1. The subset A ⊂ ${{\mathbb{Z}_N}}$ is considered as a pseudorandom subset of degree k if P_k(A, N) is “small” in terms of N. We establish a link between the Gowers norm and our pseudorandom measure, and show that “good” pseudorandom subsets must have “small” Gowers norm. We give an example to suggest that subsets with “small” Gowers norm may have large pseudorandom measure. Finally, we prove that the pseudorandom subset of degree L(k) contains an arithmetic progression of length k, where L(k) = 2·lcm(2, 4, . . . , 2|$\frac{k}{2}$|), for k ≥ 4, and lcm(a₁, a₂, . . . , a_l) denotes the least common multiple of a₁, a₂, . . . , a_l.     

On the gowers norms of certain functions

We consider functions f(x, y) whose smallness condition for the rectangular norm implies the smallness of the rectangular norm for f(x, x + y). We also study families of functions with a similar property for the higher Gowers norms. The method of proof is based on a transfer principle for sums between special systems of linear equations.     

Large values of the Gowers-Host-Kra seminorms

The Gowers uniformity norms of a function f: G → C on a finite additive group G, together with the slight variant defined for functions on a discrete interval [N]:= {1, ...,N}, are of importance in the modern theory of counting additive patterns (such as arithmetic progressions) inside large sets. Closely related to these norms are the Gowers-Host-Kra seminorms of a measurable function f: X → C on a measure-preserving system X = (X,X,μ, T). Much recent effort has been devoted to the question of obtaining necessary and sufficient conditions for these Gowers norms to have non-trivial size (e.g., at least η for some small η > 0), leading in particular to the inverse conjecture for the Gowers norms and to the Host-Kra classification of characteristic factors for the Gowers-Host-Kra seminorms.     

Stability results for random discrete structures

Two years ago, Conlon and Gowers, and Schacht proved general theorems that allow one to transfer a large class of extremal combinatorial results from the deterministic to the probabilistic setting. Even though the two papers solve the same set of long‐standing open problems in probabilistic combinatorics, the methods used in them vary significantly and therefore yield results that are not comparable in certain aspects. In particular, the theorem of Schacht yields stronger probability estimates, whereas the one of Conlon and Gowers also implies random versions of some structural statements such as the famous stability theorem of Erd?s and Simonovits. In this paper, we bridge the gap between these two transference theorems. Building on the approach of Schacht, we prove a general theorem that allows one to transfer deterministic stability results to the probabilistic setting. We then use this theorem to derive several new results, among them a random version of the Erd?s‐Simonovits stability theorem for arbitrary graphs, extending the result of Conlon and Gowers, who proved such a statement for so‐called strictly 2‐balanced graphs. The main new idea, a refined approach to multiple exposure when considering subsets of binomial random sets, may be of independent interest.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 269‐289, 2014     

A variant of the hypergraph removal lemma

Recent work of Gowers [T. Gowers, A new proof of Szemerédi's theorem, Geom. Funct. Anal. 11 (2001) 465-588] and Nagle, Rödl, Schacht, and Skokan [B. Nagle, V. Rödl, M. Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Regularity lemma for k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Applications of the regularity lemma for uniform hypergraphs, preprint] has established a hypergraph removal lemma, which in turn implies some results of Szemerédi [E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975) 299-345], and Furstenberg and Katznelson [H. Furstenberg, Y. Katznelson, An ergodic Szemerédi theorem for commuting transformations, J. Anal. Math. 34 (1978) 275-291] concerning one-dimensional and multidimensional arithmetic progressions, respectively. In this paper we shall give a self-contained proof of this hypergraph removal lemma. In fact we prove a slight strengthening of the result, which we will use in a subsequent paper [T. Tao, The Gaussian primes contain arbitrarily shaped constellations, preprint] to establish (among other things) infinitely many constellations of a prescribed shape in the Gaussian primes.     

The distance between two convex sets

In this paper we explore the duality relations that characterize least norm problems. The paper starts by presenting a new Minimum Norm Duality (MND) theorem, one that considers the distance between two convex sets. Roughly speaking the new theorem says that the shortest distance between the two sets is equal to the maximal “separation” between the sets, where the term “separation” refers to the distance between a pair of parallel hyperplanes that separates the two sets.The second part of the paper brings several examples of applications. The examples teach valuable lessons about the role of duality in least norm problems, and reveal new features of these problems. One lesson exposes the polar decomposition which characterizes the “solution” of an inconsistent system of linear inequalities. Another lesson reveals the close links between the MND theorem, theorems of the alternatives, steepest descent directions, and constructive optimality conditions.     

Optimality of the Lax-Wendroff condition

We show that any spectrally dominant vector norm on the vector space of matrices which is invariant under isometries dominates the numerical radius r(·). Thus, the celebrated Lax-Wendroff stability condition, r(·)?1, defines a maximal isometrically invariant stable set.     

The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic

We establish the inverse conjecture for the Gowers norm over finite fields, which asserts (roughly speaking) that if a bounded function f : V ? \mathbbC{f : V \rightarrow \mathbb{C}} on a finite-dimensional vector space V over a finite field \mathbbF{\mathbb{F}} has large Gowers uniformity norm ||f||_U^s+1(V){{\parallel{f}\parallel_{U^{s+1}(V)}}} , then there exists a (non-classical) polynomial P: V ? \mathbbT{P: V \rightarrow \mathbb{T}} of degree at most s such that f correlates with the phase e(P) = e ^2πiP . This conjecture had already been established in the “high characteristic case”, when the characteristic of \mathbbF{\mathbb{F}} is at least as large as s. Our proof relies on the weak form of the inverse conjecture established earlier by the authors and Bergelson [3], together with new results on the structure and equidistribution of non-classical polynomials, in the spirit of the work of Green and the first author [22] and of Kaufman and Lovett [28].     

BMO‐Type Norms Related to the Perimeter of Sets

In this paper we consider an isotropic variant of the BMO‐type norm recently introduced (Bourgain, Brezis, and Mironescu, 2015). We prove that, when considering characteristic functions of sets, this norm is related to the perimeter. A byproduct of our analysis is a new characterization of the perimeter of sets in terms of this norm, independent of the theory of distributions.© 2016 Wiley Periodicals, Inc.     

Compact and inessential perturbations of operators with closed range

The size of the perturbation class {SL(E)S has closed range}+I(E) is studied, whereE is a Banach space andI(E) stands for various classical operator ideals. For instance, it is shown for the ideal consisting of the inessential operators that the resulting perturbation class does not exhaust the class of bounded linear operators under natural structural conditions onE. It is known from a recent result of Gowers and Maurey that some conditions are needed.Partially supported by the Academy of Finland     

Equivalence of polynomial conjectures in additive combinatorics

We study two conjectures in additive combinatorics. The first is the polynomial Freiman-Ruzsa conjecture, which relates to the structure of sets with small doubling. The second is the inverse Gowers conjecture for U ³, which relates to functions which locally look like quadratics. In both cases a weak form, with exponential decay of parameters is known, and a strong form with only a polynomial loss of parameters is conjectured. Our main result is that the two conjectures are in fact equivalent.     

An algorithmic hypergraph regularity lemma

Szemerédi 's Regularity Lemma is a powerful tool in graph theory. It asserts that all large graphs admit bounded partitions of their edge sets, most classes of which consist of uniformly distributed edges. The original proof of this result was nonconstructive, and a constructive proof was later given by Alon, Duke, Lefmann, Rödl, and Yuster. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl gave one such extension in the case of 3‐uniform hypergraphs, which was later extended to k‐uniform hypergraphs by Rödl and Skokan. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rödl, and Skokan. Here, we give a constructive proof of a regularity lemma for hypergraphs.     

On lattice properties of the composition operator

The vector space £_b(E) of all order bounded linear operators on a Dedekind complete Riesz space E is both a Riesz space and an algebra. This note investigates the degree of compatibility between the algebraic and lattice structures of £_b(E). Two of the main results are the following:

1. An operator on a Banach lattice with an order continuous norm factors through the lattice operations if and only if it is an interval preserving Riesz homotnorphism.
2. A Dedekind complete Banach lattice E has an order continuous norm if and only if 0≤T_n ↑ T in £_b(E) implies T _n ² ↑ T².

     

Unbounded disjointness preserving linear functionals and operators

Let E and F be Banach lattices. We show first that the disjointness preserving linear functionals separate the points of any infinite dimensional Banach lattice E, which shows that in this case the unbounded disjointness preserving operators from \({E\to F}\) separate the points of E. Then we show that every disjointness preserving operator \({T:E\to F}\) is norm bounded on an order dense ideal. In case E has order continuous norm, this implies that every unbounded disjointness preserving map \({T:E\to F}\) has a unique decomposition T = R + S, where R is a bounded disjointness preserving operator and S is an unbounded disjointness preserving operator, which is zero on a norm dense ideal. For the case that E = C(X), with X a compact Hausdorff space, we show that every disjointness preserving operator \({T:C(X)\to F}\) is norm bounded on a norm dense sublattice algebra of C(X), which leads then to a decomposition of T into a bounded disjointness preserving operator and a finite sum of unbounded disjointness preserving operators, which are zero on order dense ideals.     

Density theorems and extremal hypergraph problems

We present alternative proofs of density versions of some combinatorial partition theorems originally obtained by E. Szemerédi, H. Furstenberg and Y. Katznelson. These proofs are based on an extremal hypergraph result which was recently obtained independently by W. T. Gowers and B. Nagle, V. Rödl, M. Schacht, J. Skokan by extending Szemerédi’s regularity lemma to hypergraphs.     

图的极大Tutte集的几个有效算法

图G=(V,E)的Tutte集定义为X■V(G)满足ω_o(G-X)一|X|=def(G).若不存在Tutte集Y■X,则称X为图G的极大Tutte集.通过找极大extreme集和D-图的极大独立集给出一般图G的找极大Tutte集的两个有效算法,并给出结论:X■V(G)是二部图G的极大Tutte集当且仅当X为二部图G的最小覆盖,从而得到找二部图G的极大Tutte集的一个有效算法.     

Norm behaviour of solutions to a parabolic–elliptic system modelling chemotaxis in a domain of ℝ3

In this paper, we study a parabolic–elliptic system defined on a bounded domain of ?³, which comes from a chemotactic model. We first prove the existence and uniqueness of local in time solution to this problem in the Sobolev spaces framework, then we study the norm behaviour of solution, which may help us to determine the blow‐up norm of the maximal solution. Copyright © 2004 John Wiley & Sons, Ltd.     

The number of maximal independent sets of (k + 1)-valent trees

We classify maximal independent sets of (k + 1)-valent trees into two groups, namely, type A and type B maximal independent sets and consider specific independent sets of these trees. We study relations among these three types of independent sets. Using the relations, we count the number of all maximal independent sets of (k + 1)-valent trees withn vertices of degreek + 1.     

A strong form of spectral resolution

Summary We consider pseudo-measures T on totally disconnected sets E as finitely additive set functions whit the usual variation norm ‖ ‖_v. If , m(E)=0, T=f′, f ∈L ¹, and ‖T‖_v<∞ then T is a measure. For arbitrary locally compact abelian groups we give conditions that T be a measure in terms of the pseudo-measure norm; this result is known for R/2ΠZ. Entrata in Redazione il 5 gennaio 1969.