{'fraction_non_alphanumeric': 0.055138217956629994, 'fraction_numerical': 0.015768977038156242, 'mean_word_length': 3.730420777129052, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 38, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Graphons arising from graphs definable over finite fields

We prove a version of Tao's algebraic regularity lemma for asymptotic classes in the context of graphons. We apply it to study expander difference polynomials over fields with powers of Frobenius.

1. Introduction 1.1. Historical overview and the statement of results. Tao's algebraic regularity lemma is a variant of the celebrated Szemerédi's regularity lemma that applies to graphs that can be defined by a first-order formula over finite fields. It states that such a graph can be decomposed into definable pieces which are roughly about the same size and such that the edges between those pieces behave almost randomly. This process is referred to as regularisation. It was proved by Tao in [23] in order to study expander polynomials over finite fields, and initially it was formulated for fields of large enough characteristics.
Further developments on Tao's lemma have a somewhat complex history. In a private correspondence to Tao, Hrushovski [10] gave another proof of the lemma using the model-theoretic tools for studying the growth rates of definable sets over finite fields, as developed by Chatzidakis-van den Dries-Macintyre in [6]. Independently, Pillay and Starchenko gave an analogous proof in the preprint [19]. The advantage of these proofs is that they remove the requirement of the large characteristics of the field. Pillay and Starchenko state that their proof also works for 'measurable' structures studied in the the context of asymptotic classes of finite structures by Macpherson-Steinhorn [16] and Elwes and Macpherson [8]. Garcia-Macpherson-Steinhorn [9] state, without proof, a version of the lemma for classes of finite structures controlled by suitable pseudofinite dimensions, which potentially generalise asymptotic classes.
In this paper we give a proof of Tao's algebraic regularity lemma for finite fields of any characteristics using concepts from the theory of graphons, and we adapt the lemma to relative asymptotic classes. We apply it to study expander difference polynomials over fields with powers of Frobenius. As far as the algebraic regularity lemma for fields goes, our proof benefited from the strategy used in the revisited and simplified proof of his lemma by Tao in his blog article [22].
Upon writing a preliminary version of this article, we received a copy of [10]. We now understand that Hrushovski envisaged in that letter that Tao's regularity lemma applies to fields with Frobenius (1.4, 7.5 and that Tao's algebraic constraint is directly related to the existence of a model-theoretic group configuration.

1.2.
Graphons. The space of graphons with the cut metric is known as one of the most suitable contexts for studying the limit behaviour of (dense) finite graphs, as detailed in [14].
It is also extremely useful for formulating and proving regularity lemmas. Indeed, to express that a graph can be regularised to a certain precision, it is enough to say that it is sufficiently close to a stepfunction in the space of graphons, a piecewise constant probability function on the unit square encoding a rectangular array of the edge densities of pieces forming a regular decomposition of the graph, see Definition 2.4.
The algebraic regularity lemma in this context states the following, see theorems 5.4, 5.5 and Corollary 5.6.
In the space of graphons, the set of accumulation points of the family of realisations of a definable bipartite graph over the structures ranging in an asymptotic class is a finite set of stepfunctions.
Asymptotic classes are defined as classes of finite structures such that growth rates of definable sets are controlled by rational monomials 3.12. Consequently, stepfunctions appearing in the above take arbitrary rational probability values. In contrast, several recent regularity lemmas from other contexts, including [17] in stable and [7] in distal context can be viewed as 0-1 laws, and the resulting stepfunctions only take values 0 and 1.
1.3. Definable regularisation. An important feature of this note is a uniform formulation of the lemma. We emphasise that realisations of a single definable stepfunction over finite structures from an asymptotic class can be used to regularise a definable graph. The proof is almost constructive, and we carefully analyse the space of parameters needed to define the regularising stepfunction. It becomes apparent that there are finitely many possible asymptotic behaviours of its realisations as we vary the finite structures in an asymptotic class.
The strategy of proof is congenial to the context of graphons in view of the fact that we start with a general weak regularity Lemma 4.1 for graphons, and then use definability and Chatzidakis-van den Dries-Macintyre properties to dramatically improve the conclusion. 1.4. Fields with powers of Frobenius. We draw attention to the fact that the algebraic regularity lemma applies to finite-dimensional bipartite graphs definable in the language of difference rings over the class of algebraic closures of finite fields equipped with powers of the Frobenius automorphism, which was shown to be an asymptotic class in [20] (with a suitable modification to the definition of 'asymptotic class'). This is a significant generalisation of the context of finite fields and a potential new source of interesting examples. We outline the possibility of studying difference expander polynomials and we describe the difference morphisms which are moderate expanders.
1.5. Novelty in the paper. The 'bounded-complexity' statements of Tao's regularity lemma in various contexts have been (independently) known to experts. Our main proof loosely follows the strategy of the proof from [22].
The added value of this paper consists of the following contributions.
(1) The uniform statement of the result as discussed in 1.3, for a given set of formulae defining the initial graph and without the use of the notion of bounded complexity of formulae, which makes the proof more constructive. (2) It is aesthetically convenient to state the regularity lemma in the space of graphons, as noted in 1.2. (3) The profound reason for working in the space of graphons is to fix the arguments from Tao's proof [22] in a single space within the realm of classical functional analysis. While each step in his proof is formulated for operators on finite-dimensional normed spaces, the dimensions grow with each step so it is difficult to track the key objects through the changes, or to give a bound on the dimensions of relevant spaces a priori in terms of the complexity of the formulae defining the given bipartite graph.
(4) While finite fields are extensively used in combinatorics, fields with powers of Frobenius touched upon in 1.4 are less known. We hope that our treatment will introduce them to a wider audience. (5) As pointed out by Hrushovski in [10], as well as Tao in a number of talks, the hidden group structure in 'solving the algebraic constraint'-type theorems needed to discuss expanding properties of polynomials can be uncovered using the model-theoretic group configuration arguments. We present these ideas as explicitly as possible in 8.17 whilst proving the expanding dichotomy for 'difference polynomials'.
1.6. Future work. Tao's lemma, as much as the original Szemerédi's lemma, is only interesting in the context of reasonably dense graphs. After much research on obtaining an analogue of Szemerédi's lemma for sparse graphs, as reported by Kohayakawa in [13], such an analogue was found by Scott in [21]. In further work we hope to extend our ideas from graphons to the Nešetřil-Ossona de Mendez notion of measurings [18] in order to obtain local versions of Tao's regularity lemma which would deal with sparse definable graphs. This seems like a viable programme in the view of Scott's lemma [21] and the fact that measurings give a unified approach to combinatorial limits which has graphons as a special case, but also applies to classes of sparse graphs.
1.7. Acknowledgement. We would like to thank the anonymous referee for their dedicated work on the paper and numerous suggestions for improvements.

Background: Graphs and Graphons
The background on the space of graphons given in this section is based almost entirely on the book [14] by Lovász, presented with minor modifications needed to treat our 'bipartite/non-symmetric' version of kernels and graphons.
(1) The space of kernelsW is the space of the equivalence classes of essentially bounded measurable functions [0, 1] 2 → R modulo equivalence up to a measure 0 set, i.e., the underlying vector space ofW is L ∞ ([0, 1] 2 ). Following the usual conventions, we often abuse the notation and speak of 'functions' or 'kernels' (and 'graphons' below) in terms of functions rather than the equivalence classes of functions, by taking representatives and by using the notation W in place ofW . Sometimes we need to be more explicit, for example a suitable metric onW will be introduced below, but it is only a pseudo-metric on W .
(2) The space of graphons is (3) We write The inequalities are given up to a measure zero set (see Definition 2.3).
Remark 2.2. The classical literature on graphons [14] usually stipulates that kernels and graphons have to be symmetric functions, and we write W sym , W sym 0 and W sym 1 for the corresponding spaces. Given that we are primarily interested in studying the limits of bipartite and directed graphs, we do not assume the symmetry, but our context is easily reconciled with the classical one through the map W → W sym , assigning to every W ∈ W the symmetric 'bipartite kernel' elsewhere.
Here W * denotes transpose kernel of W , defined by The above map will yield a closed embedding in the cut metric from 2.13 and will preserve the membership in W , W 0 and W 1 , which allows us to resort to the classical theory of symmetric graphons whenever needed.
We often informally refer to the number max(m, n) as the number of steps of the stepfunction as above.
(1) for i ∈ U, we have a positive real weight w i ; (2) for j ∈ V , we have a positive real weight w j ; (3) for each edge (i, j) ∈ E, we have a weight w ij ∈ R.
The above assignment can be extended to U ×V by stipulating that w ij = 0 whenever (i, j) is not an edge.
Definition 2.6. Let Γ = (U, V, E ⊆ U × V, w) be a finite weighted bipartite graph. We define the associated stepfunction by considering the partitions [0, 1] = i∈U U i and [0, 1] = j∈V V j with lengths µ(U i ) = w i /w U and µ(V j ) = w j /w V , where w U = i∈U w i , w V = j∈V w j , and by letting By a slight abuse of notation, whenever we wish to consider a graph Γ in the space of graphons, we implicitly identify Γ with W (Γ). Notation 2.7. Let Γ be a finite edge-weighted bipartite graph, i.e., a weighted bipartite graph with all node weights 1, and let A = (w ij ) be its matrix of edge weights. We write In particular, we use the notation for the constant kernel with value w.

Kernel operators.
Definition 2.8. The kernel operator T W : L 1 [0, 1] → L ∞ [0, 1] associated to a kernel W ∈ W is defined by Remark 2.9. Considered as an operator L 2 [0, 1] → L 2 [0, 1], T = T W is a Hilbert-Schmidt operator; it is a compact operator, with a singular value decomposition where {u i } and {v i } are orthonormal sets and σ i are positive with σ i → 0 such that the Hilbert-Schmidt norm satisfies The spectrum of T is discrete, and the nonzero eigenvalues λ i satisfy lim i λ i = 0. If W is symmetric, the eigenvalues λ i are real and we have a spectral decomposition where f k is the normalised eigenfunction corresponding to the eigenvalue λ k .

Operations on kernels.
Definition 2.10. Let W i be a countable family of kernels, and let a i and b i be positive real numbers with i a i = 1 and i b i = 1. The direct sum of kernels W i with weights (a i , b i ), denoted is defined as follows. We partition the interval [0, 1] into intervals I i of lengths a i and also into intervals J i of lengths b i . We consider the monotone affine maps ϕ i mapping I i onto [0, 1], and ψ i mapping J i onto [0, 1], and we let A kernel is said to be connected, if it is not isomorphic up to a null set to a non-trivial direct sum of kernels.
Apart from the obvious linear structure, we consider the following operations on W . Definition 2.11. Let U and W be two kernels.
(2) Their operator product is the kernel Remark 2.12. If U and W are kernels, then, considering the associated kernel operators as operators on L 2 [0, 1], we have    (1) We say that Γ is ǫ-homogeneous of density w ∈ [0, 1] provided, for every A ⊆ U and B ⊆ V , (2) We say that Γ is ǫ-regular of density w ∈ [0, 1] if, for every A ⊆ U with |A| > ǫ|U| and B ⊆ V with |B| > ǫ|V |, The well-known connection between regularity lemmas (the existence of a homogeneous partition) and the cut metric (see the discussion following 9.3 in [14]) is explained in the following lemma.
is ǫ-homogeneous with density w ij . LetΓ be a weighted bipartite graph on U, V such that all vertices have weight 1 and all edges between U i and V j have weight w ij . Then Proof. Item (1) follows from definitions of homogeneity, associated graphon and cut distance. Suppose that Γ satisfies the assumptions of (2). If we writē U i andV j for segments in [0, 1] corresponding to U i and V j in W (Γ), using (1), we obtain that, for measurable A i ⊆Ū i and B j ⊆V j , Hence, for measurable A, B ⊆ [0, 1], we obtain

2.7.
The space of graphons. The cut distance is only a pseudo-metric on W 0 , so here we work with W 0 , the metric space of classes of graphons at non-zero distance. While all this is standard for a logician, we hope to improve the exposition for a reader with a combinatorics background by adopting the following notation inspired by category theory. Let C be an arbitrary category of structures for a fixed first-order language L with (substructure) embeddings as morphisms, and let C ≺ be the subcategory in which the morphisms are elementary embeddings.
Given a first-order formula ϕ(x) in the language L in variables x = x 1 , . . . , x n , we define the assignment mapping a structure F in C to the set of realisations of the formula ϕ in F .
If ϕ is a sentence in the language L, theñ For each formula ϕ, the restriction ofφ to C ≺ is a functor On the other hand, while A n : C → Set is a functor, the assignment ϕ : C → Set for an arbitrary formula ϕ(x) in variables x = x 1 , . . . , x n (or a sentence) is at best a subassignment of A n , i.e., for all F ∈ C, Definition 3.1. A subassignment S of some A n with n ≥ 0 is called a definable set if it is equivalent to the assignmentφ associated with some first-order formula ϕ(x) in n variables.
We often emphasise that such sets are 'parameter-free', or 'defined with no parameters'. Remark 3.2. If X and Y are definable sets, their argument-wise cartesian product, denoted If X, Y ⊆ A n are definable, so are the following sets is a definable subset of Y.
from a definable set X to an arbitrary set E is determined by a choice of (1) finitely many values e 1 , . . . , e n ∈ E, and (2) finitely many definable subsets X i ⊆ X, i = 1, . . . , n, so that, for every F ∈ C, We stipulate that, for X = A 0 , the X i are associated with sentences ϕ i such that, for every F ∈ C, In the following, we discuss definable sets with parameters. We start by a construction allowing us to choose parameters from a fixed structure in our class, and continue onto constructions of definable parameter spaces. Definition 3.6. Let F ∈ C, and let L F be the language obtained by adding the constant symbols for the elements of F to L. Let C F be the subcategory of C consisting of superstructures of F . If ϕ(x; c) is a formula in the language L F with parameters c = c 1 , . . . , c m ∈ F , then we can define the assignment and it is again a definable set over S. Given s ∈ S(F ) for some F ∈ C, We can consider the singleton {s} as a definable set with parameters from F over S, so we obtain a definable set which is called the fibre of X over S with parameter s, and it is a definable set over F in the sense of 3.6 via Remark 3.9. By the above, a definable set X over S gives rise to a family of definable sets X s parametrised by parameters s from S.
In model theory, this object is usually called a uniformly definable family of definable sets. The reason for our specific formulation is the additional precision needed to treat parameters over a family of structures, as opposed to working in a fixed 'monster model', which is the most familiar setting for model theory.
Note, if X is a definable set, it can naturally be considered as a definable set over A 0 . Indeed, we consider the definable map which takes X(F ) to ⊤ if and only if X(F ) = ∅. Definition 3.10. Let X be a definable set over S and let E be a set. A definable function f : X → E over S on a class of structures C is determined by a choice of (1) finitely many definable functions e 1 , . . . , e n : S → E, and (2) finitely many definable sets X 1 , . . . , X n over S such that, for every F ∈ C, every s ∈ S(F ), we have

Counting and asymptotic classes.
Definition 3.11. Let C be a class of finite structures (considered a category with substructure embeddings). We say that C is a CDM-class, if, for every definable set X over S, there exist so that, for every F ∈ C and every s ∈ S(F ), Definition 3.12. Let C be a class of finite structures (considered a category with substructure embeddings). We say that C is an asymptotic class (in the sense of [16] and [8]), if, for every definable set X over S, there exist (1) a definable function µ X : S → Q, (2) a definable function d X : S → N, so that, for every ǫ > 0 there exists a constant N > 0 such that for every F ∈ C with |F | > N and every s ∈ S(F ), Definition 3.13. Let C be a class of structures with a given function We say that C is a CDM-class relative to χ, if for every definable set X over S, there exist so that, for every F ∈ C and every s ∈ S(F ), We define an asymptotic class relative to χ analogously, to reflect the error term from 3.12.
Terminology 3.14. With notation of 3.13, we may informally refer to the number µ X (s) as measure, and to the number d X (s) as dimension.
We say that X → S is of finite relative dimension, provided d X maps into N.
Remark 3.15. Suppose X is of finite relative dimension over S, over a class C that is an asymptotic class relative to χ. For each definable subset Y of X over S, we obtain a definable probability function otherwise.
By the above definitions, for F ranging over C and s ∈ S(F ), the expressions If Y is lower-dimensional than X, then the above expressions are O(χ(F ) −1 ) . Remark 3.16. A (relative) asymptotic class is clearly a (relative) CDMclass. A CDM-class is a relative CDM-class of finite structures with respect to the cardinality function such that all definable sets are finite dimensional. Similarly, an asymptotic class is a relative asymptotic class of finite structures with respect to the cardinality function such that all definable sets are finite dimensional.
Example 3.17. The class of finite fields was shown to be a CDM-class in the foundational paper [6] by Chatzidakis-van den Dries-Macintyre.
Following a discussion of difference fields in Section 7, we will explain in 7.3 how fields with powers of Frobenius constitute a relative CDM-class by the main theorem of [20].
For further examples of CDM-classes and a discussion of differences between CDM and asymptotic classes we refer the reader to [16].

A weak regularity lemma
In this section we show that an iterate of a graphon can be regularised in infinity norm. It is a general result for graphons and, although it does not use definability, it will serve as an important first step in the proof of our main theorem later.
We reformulate the first part of the proof of [22,Lemma 3] in the language of graphons. Let associated with the graphon W . Its adjoint T * is given by Cauchy-Schwarz inequality yields that for all f ∈ L 2 ([0, 1]), and similarly, for g ∈ L 2 [0, 1], We can apply the singular value decomposition to the Hilbert-Schmidt operator T , which gives On the other hand, we obtain the Hilbert-Schmidt norm bound Using as well as (4.1), (4.2), we obtain We use these bounds to find a low rank approximation to the sixth power Intuitively, taking a high power 'tames' any unpredictable behaviour of T and produces a more manageable operator. The above operator can be diagonalised as Given an ǫ > 0, we split Using (4.4), we discretise By the choice of δ, and arguments analogous to the above, we get that Thus, we have decomposed Using (4.3), the number of summands in the definition of A is at most 1/ǫ 2 . We partition where V j = V j,ǫ are the intersections of the level sets of the y ′ i (removing any empty cells to ensure the V j are all non-empty), and The (sought-after) integral kernel W ′ of A ′ is constant on each V j × V k , so the integral kernel of T T * T T * T T * fluctuates by at most 2ǫ 2 on each V j × V k .

Algebraic regularity lemma
Definition 5.1. A definable bipartite graph over S is a triple Γ = (U, V, E), where U, V, E ⊆ U × V are definable sets over S. For each F ∈ C and each point s ∈ S(F ), we obtain a bipartite graph We are interested in describing the (limit) behaviour of the graphs Γ s (F ) as F and s vary over an asymptotic class C.
Definition 5.2. Let U, V be definable sets over S. A definable stepfunction on U × V over S is a definable function W : U × V → R over S such that there exist definable sets U 1 , . . . , U m and V 1 , . . . , V n over S so that, for each F ∈ C and each s ∈ S(F ), For F ∈ C and s ∈ S(F ), by a slight abuse of notation, we will often identify the weighted graph W s (F ) with its associated stepfunction W (W s (F )) ∈ W 0 .
and analogously for V j . We can partition S = S 1 ∐ · · · ∐ S r so that, for all s ∈ S l (F ), Thus, using 3.15, up to isomorphism, the stepfunction associated to W s (F ) through 2.6 is within o(1) from a stepfunction associated to a weighted bipartite graph with vertex weights {µ il : i} and {ν jl : j} and edge weights {e ijl : i, j} in · 1 -norm, and hence, by Fact 2.14, in the cut norm.
In fact, the net of graphons associated to the graphs {W s (F ) : s ∈ S l (F )} with respect to the preorder induced by χ(F ) has a stepfunction as a limit in the · 1 -norm.
Theorem 5.4 (Tao's algebraic regularity lemma for asymptotic classes). Let Γ = (U, V, E) be a definable bipartite graph of finite relative dimension over a definable set S on an asymptotic class C relative to χ. Then there exists a definable setS over S and a definable stepfunction W overS such that for every ε > 0, there exists an M > 0 such that for every F ∈ C with We will prove Theorem 5.5 because of the more interesting/precise analysis of the error term, and the proof of Theorem 5.4 follows along the same lines. We follow the ideas from the proof of [22,Lemma 3].
Proof. For simplicity of notation, we will write the proof for a CDM-class. Note that, because of the assumption of finite relative dimension, the same proof will work for a relative CDM-class by replacing every instance of |F | by χ(F ), for F ∈ C.
The idea is to improve this result by using the definability of Γ and the constraints on the growth rates of the sets of realisations of definable sets over CDM-classes in the spirit of 3.15.
Let us name the key objects. For F ∈ C and an s ∈ S(F ), let T = T s : The proof consists of the following conceptual steps.
(1) By the definability of Γ, the set of relevant CDM-growth rates of certain definable invariants of Γ is finite and hence separated by some minimal distance δ. We choose an ǫ > 0 small enough with respect to δ, and we construct a definable stepfunction W with at most N(ǫ) steps anticipating all the possible behaviours that may occur in regularising each Γ s (F ) for varying F ∈ C and s ∈ S(F ). (2) We verify that, for any large enough F ∈ C, any s ∈ S(F ), writing W s = W (Γ s (F )), any (not necessarily definable) stepfunction with at most N(ǫ) steps that regularises W 6 s and (W * s ) 6 in view of 4.1, turns out to be close to the steps of a realisation of W constructed in (1) in the supremum norm.
(3) From (1) and (2), it follows that W s is close to a realisation of W in the cut metric, which shows the required regularity.
Step 1. We will use the definability of Γ and decide on an appropriate choice of ǫ. The integral kernel K 3 (v, v ′ ) = K 3,s (v, v ′ ) of T T * T T * T T * for T = T s is explicitly given as Using 3.11, we get that there exists a a definable function c = c(v, v ′ , s) symmetric in v, v ′ such that, for all F ∈ C, s ∈ S(F ) and v, v ′ ∈ V s (F ), Replacing the role of T s by T * s , we consider the integral kernel K * 3,s (u, u ′ ) of T * T T * T T * T , and we similarly find a definable function c * = c * (u, u ′ , s) symmetric in u, u ′ such that for all F , s ∈ S(F ) and u, u ′ ∈ U s (F ), The set of values of c and c * is finite, so its elements are separated by some minimal distance δ > 0.
Let us choose an ǫ ∈ (0, 1) such that expresses that s ′ = (v 1 , . . . , v n , s) can serve as parameters for a definable stepfunction on V s with steps V 1,s ′ , . . . , V n,s ′ and values c( . . , Vn ,s ′ are the top-dimensional steps that we will call large in the sequel. Let Sn ,n → S be the definable set associated with the formula ψn ,n , and let S V → S be the disjoint union of all the Sn ,n forn ≤ n ≤ N(ǫ). For each i ≤ n, we have a definable set V i,n,n → Sn ,n → S V .
Analogously, using c * in place of c, for everym ≤ m ≤ N(ǫ) we construct definable sets U j,m,m → S * m,m → S U , for j ≤ m, which form steps of a definable stepfunction with values c * . Using 3.11 again, for each i,n, n and j,m, m as above, there is a definable function f j,m,m,i,n,n : S * m,m × S Sn ,n → Q such that for all F ∈ C, and s ′ ∈ S * m,m (F ), s ′′ ∈ Sn ,n (F ) mapping onto s ∈ S(F ),

LetS
We consider the definable stepfunction W overS which is given by Let us consider F ∈ C with |F | ≥ M, a parameter s ∈ S(F ) and the stepfunction W s = W (Γ s (F )).
We apply Proposition 4.1 to W s for the ǫ chosen in Step 1, and this yields a partition V s (F ) = V 1 ∐ · · · ∐ V n into n ≤ N(ǫ) sets V i so that the integral kernel K 3 (v, v ′ ) fluctuates by less than δ/2 on each V i × V j . On the other hand, by (5.1), and the choice of F , each value of K 3 (v, v ′ ) is within δ/2 from a value of the definable function c. Hence we can improve the near-constancy to the property Note that K 3 is symmetric, so γ ij will be symmetric too. Moreover, by reducing the number of V i , we can assume that γ ij = γ i ′ j for all j ∈ {1, . . . , n} implies i = i ′ , i.e., that the array γ is reduced.
Note, if v i ∈ V i for i ∈ {1, . . . , n} are parameters, then V i is definable as Hence, choosing parameters s ′ = (v 1 , . . . , v n , s) ∈ Sn ,n,s (F ) determines V i up to a permutation σ preserving γ i,j . Moreover, for a fixed s ′ we may relabel the V i so that V i = V i,n,n,s ′ (F ).
Note that V i,n,n for i ≤n are large, so 3.11 gives that for some positive a i ∈ Q, while for i >n, dim(V i,n,n,s ′ ) < dim(V ) and LetV j ⊆ [0, 1] denote the segment corresponding to a large step V j in the stepfunction W s associated to the graph Γ s (F ) via 2.6. Suppose g ∈ L 2 [0, 1] is supported onV j with mean zero. Combining (4.5) and (5.4), we obtain On the other hand, Bessel's inequality gives and so Hölder's inequality (combining these two inequalities via A.3) shows that Similarly, arguing for K * 3 (u, u ′ ), we can find a partition U s (F ) = U 1 ∐ · · · ∐ U m with m ≤ N(ǫ) so that, upon fixing a parameter s ′′ = (u 1 , . . . , u m , s) ∈ S * m,m,s (F ), by relabeling U j , we have U j = U j,m,m,s ′′ (F ). Moreover, when f is supported on one of the segmentsŪ i corresponding to a large step U i with mean zero.
Step 3. Let W be the definable stepfunction overS defined in Step 1. We claim that fors ∈S(F ) which maps to s ′ and s ′′ from Step 2, d (W s , Ws(F )) ≪ |F | −1/12 .

Combining the estimates obtained in
Step 2 with the Cauchy-Schwarz inequality, we deduce that | T f, g 2 | ≪ |F | −1/12 f 2 g 2 whenever f and g are supported onV i andŪ j with at least one of f , g of mean zero.
For measurable A ⊆Ū i and B ⊆V j , we decompose the characteristic functions into sums of mean-zero and constant functions. Note that the mean-zero parts are bounded by 1. We obtain that On the other hand, using 5.3, Thus, for measurable A ⊆Ū i and B ⊆V j , we have

For arbitrary measurable
where the summation is over the large blocks and, by (5.6), and the behaviour over non-large/lower-dimensional blocks is absorbed by the O(|F | −1 ) term. The last inequality follows from Jensen's inequality. The desired conclusion follows from the fact thatm andn are bounded independently of F . Combining 5.3 and 5.4, we obtain the following. Corollary 5.6. Let Γ be a definable graph of finite relative dimension over S on an asymptotic class C relative to χ. The set of accumulation points of the family of finite graphs in the spaceW 0 of graphons has a set of representatives which is a finite set of stepfunctions.

Finite fields
The original algebraic regularity lemma by Tao in [23] was formulated for graphs definable in the language of rings over finite fields. We give several examples of graphons arising in this context by along the lines of our graphon formulation 5.6.
We are interested in accumulation points in the graphon space of the set of graphs Γ(F q ), as F q ranges over all finite fields (these are in fact a symmetric variant of the well-known Paley graphs). When char(F q ) = 2, being a square is an event of 'CDM probability' (in the sense of 3.15) 1/2. Thus, the edge density is approximately 1/2 and these graphs accumulate around the constant graphon W (1/2). These graphs are interesting in model theory due to the fact that their ultraproduct limit is the random graph.
For char(F q ) = 2, everything is a square, so the graphs accumulate around the constant graphon W (1).
The definable stepfunction W : Hence, the set of accumulation points is The definable sets Let W be the definable function which returns 1 on U 0 × U 0 ∪ U 1 × U 1 and 0 elsewhere. The definable stepfunction W regularises Γ, and the set of accumulation points of Γ(F q ) in the space of graphons is where the former denotes the stepfunction associated to the graph with edge weights matrix 1 0 0 1 as in 2.7, which is the accumulation point of Γ(F q ) for odd q, and the latter is the constant graphon 1, which is the accumulation point of Γ(F q ) for even q.
In the following example, unlike in Example 6.1, the limit behaviour is not determined by the characteristic only. Example 6.3. Let us define the graph Γ on A 1 through the edge relation In fact, the set of cubes in F q is of size (q − 1)/3 + 1 if 3|q − 1 and of size q otherwise.
The first condition happens precisely when the primitive cube root of unity belongs to F q , which is expressible by the first-order condition ∃t t 3 = 1 ∧ t = 1 so Γ is definably regularised. To conclude, the graphs Γ(F q ) accumulate around W (1/3) when 3|q − 1, and around W (1) otherwise.
The following example illustrates the need to introduce parameters. Example 6.4. Consider the graph Γ on A 1 with the edge relation The graph is trivially considered over the base S = A 0 . Let S(z) ≡ z 3 = 1 ∧ z = 1, and consider the definable sets U i overS, i = 0, 1, 2: We see that Γ is regularised by the definable stepfunction W(x, y; z) over S taking value 1 on U 0 × U 0 ∪ U 1 × U 2 ∪ U 2 × U 1 and 0 elsewhere, and the graphs Γ(F q ) accumulate around the stepfunction consisting of a commutative ring with identity R and an endomorphism σ : R → R. We call it a difference field if R happens to be a field. A homomorphism of difference rings is a ring homomorphism f : R → S satisfying The category of difference rings is denoted by

σ-Rng
A difference ring (R, σ) is a transformal domain if R is a domain and σ is injective.
Notation 7.1. For a prime power q, we write for the difference field consisting of the algebraic closure of a finite field, together with a power of the Frobenius automorphism ϕ q (x) = x q .

7.2.
Counting points over fields with Frobenius. In [20], we established the following difference analogue of [6].
a constant C X > 0, so that, for every K q with q > C X and every s ∈ S(K q ), Corollary 7.3. The class C of fields K q for prime powers q is a CDM-class relative to the function χ(K q ) = q.
Remark 7.4. An alternative approach to 7.3 is to study finite fields with powers of Frobenius, which requires the study of N-dimensional asymptotic classes. The authors of [9] go even further, and note that Tao's regularity lemma applies in classes of structures with pseudofinite dimension.
7.3. Algebraic regularity lemma for fields with Frobenius. Using the fact 7.3 that fields with Frobenius constitute a relative CDM-class and regularity lemma 5.5, we obtain the following.
Corollary 7.5. Let Γ = (U, V, E) be a definable bipartite graph of finite relative dimension over a definable set S in the language of difference rings. There exists a constant M = M(Γ) > 0, a definable setS over S and a definable stepfunction W overS such that for every K q with q > M, everỹ s ∈S(K q ) mapping onto s ∈ S(K q ), Example 7.6. Let U(x) ≡ xσ(x) 2 = 1, and let Γ be a graph on U × U with the edge relation E(x, y) ≡ ∃z ∈ U xy = z 3 .
Then U(K q ) is the group µ 2q+1 of (2q + 1)-th roots of unity inF q , and the size of the set of cubes depends on whether µ 3 ⊆ µ 2q+1 , i.e., whether 3|2q + 1. Henceforth we can follow the reasoning from Example 6.4 and we obtain the same limit stepfunctions. On the other hand, let us point out that the graphs Γ(K q ) cannot be obtained from a graph interpretable over finite fields, which shows that the difference context is genuinely richer. Indeed, already in even characteristic, for each q, the smallest finite field containing the set µ 2q+1 = U(K q ) is F 4q 2 , so the size of the set of realisations grows roughly as the square root of the size of the corresponding finite field, which cannot happen by the CDM-property 3.11 proved for finite fields in [6].
Example 7.7. Let Γ be defined on the same U as in Example 7.6, but with E(x, y) ≡ ∃z ∈ U xσ(y) = z 3 .
A morphism between affine difference schemes is a natural transformation We shall only ever discuss affine difference schemes, so we omit the word 'affine' form our descriptions. The category of difference schemes is denoted σ-Sch.
Definition 8.5. Given S ∈ σ-Sch, a difference scheme over S is a morphism X → S. A morphism between schemes X → S and Y → S is given by a morphism X → Y which commutes with the structure morphisms to S, as in the commutative diagram from 3.7. We obtain the category of difference schemes over S, σ-Sch /S . Remark 8.6. By Yoneda's lemma, if X is associated with a difference ring (A, σ) and Y with (B, σ), a morphism X → Y always arises from a difference ring homomorphism (B, σ) → (A, σ), whence the category of difference schemes is opposite to that of difference rings, Moreover, if S corresponds to a difference ring (k, σ), then σ-Sch /S ≃ ((k, σ)-Alg) op . Definition 8.7. Let f : X → S be a morphism of difference schemes associated with a difference ring homomorphism (k, σ) → (A, σ). We say that Example 8.9. The set of solutions of the difference equation σx = x in the difference field K q = (F p , ϕ q ) is the finite field F q .
Remark 8.10. Let S be a difference scheme assocatied with a difference ring (k, σ), and consider a system of difference polynomial equations . . .
where f i ∈ k[x 1 , . . . , x n ] σ , and consider the difference scheme X over S associated to the (k, σ)-algebra of finite σ-presentation For any (k, σ)-algebra (R, σ), the set of (R, σ)-rational points can be identified with the set of solutions of the above system in (R, σ), i.e., the intersection of the solution sets of all equations f i = 0 in (R, σ). This observation clarifies how a difference scheme of finite presentation can be considered a (quantifier-free) definable set as in 3.1.
Definition 8.11. Let f : X → S be a morphism of difference schemes of finite σ-presentation over Z, and let C be the relative CDM-class of fields with Frobenius K q = (F p , ϕ q ). We say that (1) f is of finite relative dimension, if it is such when considered as a definable map over C in the sense of 3.14; (2) f is dominant, if the dimension of its image as the definable set is of full dimension in S; (3) f is finite, if the map f (K q ) between realisation sets has finite fibres for all K q ∈ C; (4) f is generically finite, if it fails to have finite fibres only over a lowerdimensional subset of S.
Remark 8.12. All of the above properties of difference schemes and their morphisms have intrinsic formulations rooted in difference algebra, as given in [11] and [20]. In particular, the notion of total dimension of difference schemes is shown to agree with the CDM-dimension in [20]. We choose these equivalent formulations in order to simplify the presentation.
Terminology 8.13. Following the comparison of difference schemes to definable sets made in 8.10, we shall no longer use the boldface notation to denote difference schemes.
Definition 8.14. Let X and Y be difference schemes. A correspondence X Y is given by a difference scheme W ⊆ X ×Y such that the projection W → X is dominant with generically finite fibres.
8.2. Algebraic constraint and group configuration. The results in this subsection parallel those of Tao in [23].
Definition 8.15. Let S be a transformally integral difference scheme of finite σ-presentation over Z and let X 1 , . . . , X n , Y be difference schemes of finite σ-presentation and finite relative dimension over S, and let f : X 1 × S · · · × S X n → Y be a morphism of difference schemes over S. We say that f is a moderate asymmetric expander if there exist constants c, C > 0 such that, for every difference field K q = (F p , ϕ q ), every s ∈ S(K q ) and every choice of Assumption 8.16 (Expansion dichotomy). Let X, Y, Z be difference schemes of finite σ-presentation over a transformally integral S with geometrically transformally integral fibres of finite relative dimension, and let f : X × S Y → Z be a morphism of difference schemes over S. Then at least one of the following statements hold: is not dominant. (2) (Moderate expansion property). There exists a σ-localisation S ′ of S and a constant C > 0 such that for every K q , every s ∈ S ′ (K q ), and In particular, the morphism f is a moderate asymmetric expander above S ′ .
We have gone through the steps and methods used in the proof of [23, Theorem 38] and consider that they can be followed formally to derive the above statement from 7.5. On the other hand, writing out the full proof would require us to repeat lengthy passages of Tao's work, including the self-improvement trick from [22] to obtain the error term of O(|F | −1/4 ) in 7.5 and the generalisation of the regularity lemma 7.5 to hypergraphs following [23,Theorem 35].
Theorem 8.17 (Solving the algebraic constraint in dimension 1). With notation of 8.16, assume that X, Y and Z are of relative dimension 1 over S and that the morphism is not dominant. Then there exists a generically finite morphism S ′ → S and an algebraic group scheme (A, * ) over S ′ , which is either G a , G m or of an elliptic curve over S ′ , and correspondences χ : X A, υ : Y A and ζ : Z A over S ′ such that f is in correspondence with the group law on A, The proof requires a vast amount of model theory and it is no longer possible to keep our exposition self-contained, hence we provide a guide to the literature for the interested reader.
• Ultraproducts of CDM-classes are measurable structures in the sense of [16] and can be treated as simple theories, which are governed by a notion of forking independence. For background on simple theories and for the basics of forking calculus we refer the reader to [4] and [26]. • For group configuration in simple theories, we refer the reader to [2] and [25]. • Hrushovski shows in [11] that the limit theory of the relative CDMclass of fields with Frobenius is the theory ACFA of existentially closed difference fields. It is extensively studied in [5]. • For groups definable in algebraically closed fields, we shall use [3], and for groups definable in ACFA we refer to [12].
Martin Bays suggested that our proof can benefit from field-theoretic arguments specific to ACFA. We provide the summary of properties we use, which can all be found in [5]. (a) While ACFA is a simple theory, the underlying field Ω is algebraically closed, so stability theory applies to it.
(b) The model-theoretic algebraic closure of A ⊂ Ω, denoted acl(A), is the field-theoretic algebraic closure of the inversive difference subfield of Ω generated by A. (c) The forking independence is witnessed by algebraic independence in the sense that, for A, B, C ⊂ Ω, A | ⌣C B if and only if the fields acl(AC) and acl(BC) are linearly disjoint over acl(C). (d) Let a ∈ Ω, let k be a difference subfield of Ω, and let k(a) σ be the difference field generated by a over k. If tr.deg(k(a) σ /k) = 1, then σ(a) ∈ acl(k(a)) and thus a | ⌣k σ(a). This amounts to saying that the difference locus of a over k is of total dimension 1, or, equivalently, of CDM-dimension 1. Such an element also has SU-rank 1 over k. Henceforth we shall simply refer to such elements as having rank 1.
(e) The difference locus of a tuple a ∈ Ω of rank 1 elements is dense in its algebraic locus, and hence it is in a correspondence with its algebraic locus in the sense of 8.14. (f ) Given a ∈ Ω and a difference subfield k of Ω, the canonical basis Cb(a/k) is the smallest perfect difference field over which the locus of a over k is defined. It equals, in the pure field language, to the canonical base of the type of (a, σ(a), . . .) over k. It has the property that a | ⌣Cb(a/k) k. In arbitrary simple theories, canonical bases exist only as 'hyperimaginaries', and one is forced to work with bounded closure bdd as opposed to the algebraic closure. In ACFA canonical bases exist in the real word, so any occurrence of bdd below can be replaced by acl.
Proof. Our fist objective is to extract a group configuration from the algebraic constraint. We will use the context and notation of partial generic multiactions familiar from [1], [24], [2] and [25], which works in a simple setting, suitable for dealing with arbitrary asymptotic classes whose nonprincipal ultraproducts are supersimple of finite SU-rank.
An interested reader can reformulate it in purely field-theoretic language using 8.18.
The base difference scheme S is associated with a transformal domain (R, ς), so we can take its fraction field (k, ς) and work in a large model (Ω, σ) of ACFA extending it.
Let η be a scheme-theoretic generic point of S, and write X η , Y η and Z η for the generic fibres of X, Y and Z over S, considered as difference schemes over k. For simplicity of notation, all the independences and bounded/algebraic closures and types we write below will be over k.
Let (x 0 , y 0 , z 00 ) in Ω be a generic point over k on the graph of f η , i.e., x 0 ∈ X η , y 0 ∈ Y η are rank 1 points over k, with x 0 | ⌣ y 0 and z 00 = f η (x 0 , y 0 ) ∈ Z η . We may assume that z 00 | ⌣ x 0 and z 00 | ⌣ y 0 , which implies that x 0 ∈ bdd(y 0 , z 00 ) and y 0 ∈ bdd(x 0 , z 00 ). Otherwise, we would have that z 00 ∈ bdd(x 0 ) or z 00 ∈ bdd(y 0 ) and we are in a degenerate case where the function f η defines a correspondence dependent on a single variable, which leads to the conclusion of the theorem in a trivial way.
Let π ⊆ X η × Y η × Z η be the partial type over k refining the locus of (x 0 , y 0 , z 00 ) so that |= π(x, y, z) provided f η (x, y) = z and the points x ∈ X η , y ∈ Y η , z ∈ Z η are pairwise independent. It is handy to abbreviate this by writing yz |= x. Note, if yz |= x, then z ∈ dcl(xy), y ∈ bdd(xz) and x ∈ bdd(yz). Thus, π is a generic invertible multiaction as in [ The assumption of non-dominance in this context states that for all x 0 , x 1 , y 0 , y 1 , z ij = f η (x i , y j ) (or y j z ij |= x i ), the set {z 00 , z 01 , z 10 , z 11 } is dependent.
Instead of using the group configuration for simple theories at this point, we prefer to use techniques specific to ACFA to construct a definable group.
Using the fact that this is a rank 1 group configuration in (Ω, σ), the same tuple forms a group configuration over k in the underlying algebraically closed field Ω. Indeed, the independence property (1) in the field reduct is clear, and interalgebraicity property (2) follows from 8.18(b), (d). The property (3) in the reduct is follows from the description of canonical bases 8.18(f) in the field language specialised to rank 1.
The (stable) group configuration for algebraically closed fields yields an ACF-definable group (G, * ) over the algebraic closurek so that the algebraic locus of (x 0 , y 0 , z 00 ) overk is in correspondence with the group law on G. Moreover, by results of van den Dries and Hrushovski (described in [3]), there is a 1-dimensional algebraic group A 0 defined overk whose group law is in correspondence with that of G.
Using 8.18, the graph of f η is in correspondence with the difference locus of (x 0 , y 0 , z 00 ) over k, which is in correspondence with the algebraic locus of (x 0 , y 0 , z 00 ) over k, which is in correspondence with the locus of the same tuple overk, which is in correspondence with the group law in A 0 overk.
Alternatively, we could have argued, using [12, Lemma 3.3] on the 6tuple above, that the graph of f η is in correspondence with a difference definable group H overk, and, by [12,Theorem 3.1], H is virtually definably embeddable into an algebraic group A of dimension 1 overk.
In either case, the theorem lists all three possibilities for the 1-dimensional group A 0 . Moreover, A 0 is defined over a finite extension k ′ of k, so let (L, σ) be the difference extension field of (k, ς) generated by k ′ . Through standard constructibility arguments of σ-localising S to make it normal, and considering the normalisation of S in L, we obtain a generically σ-finite difference scheme S ′ → S and a group scheme A over S ′ whose generic fibre is A 0 , and correspondences over S ′ relating the morphism f and the group law in A.
Remark 8.19. Combining Assumption 8.16 and Theorem 8.17, we obtain the following.
Let X, Y , Z be difference schemes of finite transformal type and relative total dimension 1 over S, and let f : X × S Y → Z be a morphism of difference schemes over S. Then at least one of the following statements hold.
(1) The morphism f corresponds to the additive or multiplicative group law in a way described in 8.17. (1) (Cauchy-Schwartz inequality). For x, y ∈ H, we have | x, y | ≤ x y .
Note that, for p = q = 2, the above yields the Cauchy-Schwartz inequality for L 2 (X, µ).