VC-dimension of distance graphs in finite field geometries

arXiv:2609.32052 · math.CO · Submitted 2026-09-25 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: I'm Ada.

Emmy: And I'm Emmy, here with Kolya.

Ada: We're looking at the paper: "VC-dimension of distance graphs in finite field geometries".

Emmy: Here's the gist of the paper. VC-dimension of distance graphs in finite field geometries study the VC-dimension of distance graphs of large subsets of vector spaces over finite fields to establish bounds on their complexity The paper proves that for certain sets E, the distance graph Gt(E) has a VC-dimension at least k provided that E > Cqd−⌊ d−k/3 ⌋−1 This result is significant as it provides bounds on the complexity of learning tasks related to geometric configurations in finite field geometries.

Ada: VC-Dimension Definition and Context The notion of Vapnik-Chervonenkis dimension is a fundamental concept in statistical learning theory where it is used to measure the complexity of a learning task.

Emmy: The VC-dimension of H is the largest integer k for which H shatters some set of size k (if no such k exists, the VC-dimension is said to be infinite).

Ada: A common variant of Definition 1.1 is the notion of VC-dimension of a graph, which we give here.

Title and authors: Ada: So, what are they actually proving with this paper, "VC-dimension of distance graphs in finite field geometries"? They are looking at the VC-dimension of distance graphs defined by a set E within a vector space over a finite field F d q.

Emmy: The core idea is that they define the t-distance graph Gt(E) where two points are connected if their distance is exactly t, and they are proving how many configurations that graph can shatter.

Ada: They establish Theorem one point four which states that for any k between three and d, there exists a constant C depending on k, d, m and the alpha values such that if the size of E is greater than C q to the power of d minus floor of d minus k over three minus one, then Gt(E) has a VC-dimension at least k.

Kolya: So they are giving us a lower bound on complexity based on set cardinality, and they show that this bound holds for three less than or equal to d <ref:2609.32052#pg1>. It's about showing that the structure of these graphs is rich enough when the input set E is large enough.

Ada: They also have corollaries that give them specific results. For instance, corollary one point five says if you pick a set E larger than C q to the power of d minus one, then for any t that isn't zero in F q, the distance graph Gt(E) has a VC-dimension at least d.

Emmy: That’s a very strong statement because it links the set size directly to the dimension of the space itself, showing that you can achieve a complexity level related to d just by making E slightly larger than q raised to the power of d minus one.

Kolya: And corollary one point six gives a result for smaller k, stating that if your set size is bigger than C q to the power of ceil of two d over three, you can guarantee a VC-dimension of at least three for Gt(E) <ref:2609.32052#pg3>. That’s useful when you only need to know that the complexity is above a certain threshold.

Ada: So they’re giving us concrete conditions on how many points we need in F d q to get specific shattering capabilities for these distance graphs. It’s linking combinatorial geometry with statistical learning theory in a finite field setting.

Emmy: They are using techniques like counting intersections of spheres and affine subspaces to establish the necessary bounds on the number of points involved, which is key to proving Theorem one point one one <ref:2609.32052#pg1>.

The paper's summary: Ada: Now let's talk about what they suggest as improvements or how their results can be used better. One of the main things they highlight is that the exponent in Corollary one point five, which is d minus one, is sharp when you look at the orthogonality graph O(E).

Emmy: And that sharpness was shown by a theorem called Theorem four point three, which proves that for any t not zero in F q, there exists a set E inside F d q with a size close to q raised to the power of d minus one, and the VC-dimension of O(E) is at most d minus one <ref:2609.32052#pg2>.

Kolya: That's interesting because it sets an upper bound on complexity for related structures, like orthogonality graphs. So even when we look at these related graphs, we know how complex they can be bounded by d minus one if the set size is around that critical threshold.

Ada: And they also showed that this bound applies to the orthogonality graph O(E` when E is not too small, specifically when E is not smaller than S to the power of d minus ten, according to Lemma four point two <ref:2609.32052#pg2>.

Emmy: They’re essentially showing a hierarchy of complexity bounds here. If you look at these related structures, the VC-dimension stays bounded by d minus one for sets that are slightly below that critical size threshold.

Kolya: It helps us understand where the transition happens in terms of complexity when the set size changes. It’s not just a single point; it defines a region around that threshold where we have predictable bounds on VC-dimension.

Ada: And they use this to show how to bound M, which is some parameter related to the number of stars, by saying M is less than At k of E prime and E double prime.

The paper's improvements: Emmy: So wrapping up the paper "VC-dimension of distance graphs in finite field geometries," they show us that for large enough subsets E in F d q, the distance graph Gt(E) has VC-dimension at least k under a specific size condition.

Ada: And they confirm that this bound is sharp when k equals d, and they establish a minimum set size of C q to the power of d minus floor of d minus k over three minus one needed to guarantee that complexity.

Kolya: From my point of view, it’s important because it gives us a way to quantify the difficulty of learning tasks involving these geometric structures in finite fields. It tells us what kind of data size you need to expect before the problem becomes manageable or intractable for certain complexities.

Ada: Exactly. And they provide specific bounds, like if your set size is larger than C q to the power of d minus one, you can guarantee a VC-dimension of at least d for most t not zero.

Emmy: It’s a lot to take in, but it gives us tools to understand the structural limitations imposed by the geometry when we work in these finite field settings. We’ve covered the core results of this paper and how they relate to related graphs like orthogonality graphs.

Kolya: I just want to say that while they show these bounds, the caveat is that they are dependent on choosing a constant C which can be quite large depending on k, d, m, and those alpha values mentioned in Theorem one point one zero <ref:2609.32052#pg1>.

Ada: True. And the paper notes that counting intersections of spheres and affine subspaces is what allows them to count those structures, which is the method they use to get those final bounds on M less than At k of E prime and E double prime.

Emmy: So we’ve got a good handle on how set size dictates complexity in these distance graphs over finite fields, tying it all together for this paper, "VC-dimension of distance graphs in finite field geometries."

Conclusion: Ada: So we've covered how set size in F d q determines the VC dimension of distance graphs in this paper, "VC-dimension of distance graphs in finite field geometries". Basically, we found that if you make your set E big enough—specifically if its size is greater than C q to the power of d minus floor of d minus k over three minus one—then you can guarantee a VC dimension at least k.

Emmy: That’s right. And when we look at the related orthogonality graphs, like O(E), we see that they have complexity bounded by d minus one if the set size isn't too small, according to Lemma four point two and Theorem four point three. It shows a limit on how intricate those zero dot product configurations can get.

Kolya: I just want to say that these bounds are really about governing the tails of the distribution of shatterable configurations; it tells us exactly what kind of input size you need before you can expect to find a configuration that shatters everything up to k.

Ada: Right, and we saw how they proved Theorem one point four by using those counting techniques involving intersections of spheres and affine subspaces, which is what allows them to bound the number of stars involved in those shatterings.

Emmy: It’s a clever way to count the building blocks; they show that if you choose your set E correctly, you can find a star that doesn't admit any bad configurations at all.

Kolya: And when we look at Corollary one point five, it sets the size threshold around q to the power of d minus one, and for any t not zero in F q, the graph Gt(E) has a VC dimension at least d. That’s a pretty strong link between set size and dimension.

Ada: It is. And Corollary one point six gives us another threshold for smaller k; if your set E is bigger than C q to the power of ceil of two d over three, you get a VC dimension of at least three for Gt(E).

Emmy: So it’s like we have these thresholds: one for general k, one specific size bound related to d minus one, and another specific size bound related to two thirds of d. It maps out the complexity landscape very clearly.

Kolya: I just think it helps us understand the structure behind the computation; when you're looking at these distance graphs over finite fields, knowing these bounds tells you a lot about what kind of patterns exist in that space.

Ada: Exactly. So we’ve looked at how set size dictates complexity in this paper, "VC-dimension of distance graphs in finite field geometries", and found those necessary conditions for the VC dimension to reach certain levels.

Emmy: It's a solid piece of work showing how geometric constraints translate directly into learning complexity bounds in these algebraic settings.

Kolya: Next time we look at papers, we’ll see how these structural limits apply to other types of graphs or perhaps move into different finite field structures altogether.

BRIAN MCDONALD BAKAS, MOUSTAPHA DIALLO, ALEX MCDONALD

Kennesaw State University

math.CO

Submitted: 2026-09-25

Updated: 2026-11-13

Comments: Simplified proof and stronger main theorem than appeared in first version

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 89/100

The gist: VC-dimension of distance graphs in finite field geometries study the VC-dimension of distance graphs of large subsets of vector spaces over finite fields to establish bounds on their complexity The…

Key concepts

VC-Dimension
This measures the complexity of a learning task. It is the largest number k such that a set of size k can be 'shattered' by the family of functions being studied. A graph has a VC-dimension at least k if it contains a specific structure called an induced subgraph known as Sk.
t-Distance Graph Gt(E)
This is a graph where the vertices are points from set E in Fd q, and two points are connected by an edge if their distance (measured using the norm ||x - y||) equals a fixed value t. The VC-dimension analysis focuses on how complex these graphs can be based on the size of E.
k-Shattering Graph Sk
This is a specific bipartite graph used to define shattering. It has two parts, Xk and Yk, where every vertex in Xk is connected to every vertex in Yk if their indices match. Finding an induced copy of Sk within Gt(E) proves that the VC-dimension of Gt(E) is at least k.

Terminology

Summary

VC-dimension of distance graphs in finite field geometries study the VC-dimension of distance graphs of large subsets of vector spaces over finite fields to establish bounds on their complexity The paper proves that for certain sets E, the distance graph Gt(E) has a VC-dimension at least k provided that E > Cqd−⌊ d−k/3 ⌋−1 This result is significant as it provides bounds on the complexity of learning tasks related to geometric configurations in finite field geometries. p. 0

VC-Dimension Definition and Context

The notion of Vapnik-Chervonenkis dimension is a fundamental concept in statistical learning theory where it is used to measure the complexity of a learning task. The VC-dimension of H is the largest integer k for which H shatters some set of size k (if no such k exists, the VC-dimension is said to be infinite). p. 0 A common variant of Definition 1. p. 01 is the notion of VC-dimension of a graph, which we give here. p. 0 The VC-dimension of the graph G is the VC-dimension of the family H:= 1N[x]: x ∈ V. p. 0

Key Theorems and Bounds

Theorem 1.4 states that there exists a constant C = Ck,d such that if E ⊂ Fd q satisfies E > Cqd−⌊ d−k/3 ⌋−1, then Gt(E) has VC-dimension at least k. p. 1 Corollary 1. p. 1 p. 15 shows that there exists a constant C = Cd > 0 such that if E ⊂ Fd q satisfies E > Cqd−1, then Gt(E) has VC-dimension at least d for every t ∈ Fqsetminus 0. p. 1 Corollary 1.6 states that if E ⊂ Fd q satisfies E > Cq⌈2d/3⌉, then the VC-dimension of Gt(E) is at least 3. p. 1

Proof Strategy and Tools

The proof strategy involves estimating the number of k-stars in E by counting building blocks for a copy of the shattering graph Sk. The authors utilize Lemma 3. p. 11 to establish that distance graphs are almost regular, which allows them to estimate the number of stars. p. 8 Lemma 3.3 provides an estimate for the number of k-stars with affinely independent k-part. p. 8 The main proof of Theorem 1. p. 14 involves showing that there exists a k-star which does not admit a bad set. p. 0

Sharpness and Related Results

The exponent d−1 in Corollary 1.5 is shown to be sharp by considering the orthogonality graph O(E). p. 2 Theorem 4.3 proves that for any t ∈ Fqsetminus 0 there exists a set E ⊂ Fq with E ≈ qd−1 such that the VC-dimension of Gt(E) is at most d−1. p. 0 The exponent d − (⌊d/3⌋ − 1) = ⌈2d/3⌉ in Corollary 1. p. 16 is derived by applying Theorem 1. p. 14 with k = 3.

Orthogonality Graph Bounds

Lemma 4.2 establishes that for any E subset of Fd q not Sd−10, the VC-dimension of O(E) is at most d−1. p. 1 This result relies on analyzing cases where a set of points and their corresponding indicator sets shatter the graph. p. 1 Theorem 4.3 further confirms that for any t ∈ Fqsetminus 0 there exists a set E ⊂ Fq with E ≈ qd−1 such that the VC-dimension of Gt(E) is at most d−1. p. 0

Intersection Counting Techniques

The paper employs counting intersections of spheres and affine subspaces to bound the size of these intersections. Theorem 2.10 provides a bound on the number of points in the intersection of r spheres defined by affinely independent vectors. p. 3 This counting technique is crucial for bounding M in the proof of Theorem 1. p. 111. The analysis in Section 3. p. 35 leads to the final bound on M < At,k(E′, E′′). p. 4

Conclusion and Sharpness

The final result establishes that if E > Cqs then each term in (3.6) is bounded by C−p Ek+1q k, ensuring M < At,k(E′, E′′). p. 6 The exponent s = d − (⌊d/3⌋ − 1) - 1 is derived by setting r = d−k/3 + 2 in Theorem 1. p. 14. The paper also notes that the VC-dimension of Gt(Fd q) is d + 1. p. 1 The sharpness of Corollary 1. p. 15 is demonstrated by showing that the exponent d − 1 is required for the strong conclusion. p. 1 The paper concludes by noting that counting intersections of spheres and affine subspaces allows us to count intersections of spheres. p. 6

References

[1] Ruben Ascoli, Livia Betti, Justin Cheigh, Alex Iosevich, Ryan Jeong, Xuyan Liu, Brian McDonald, Wyatt Milgrim, Steven J. Miller, Francisco Romero Acosta and Santiago Velazquez Iannuzzelli. VC-dimension and distance chains in Fd q <ref:2609. p. 032052#pg12>.

[2] Ruben Ascoli, Livia Betti, Justin Cheigh, Alex Iosevich, Ryan Jeong, Xuyan Liu, Brian McDonald, Wyatt Milgrim, Steven J. p. 0 Miller, Francisco Romero Acosta and Santiago Velazquez Innuzzelli. VC-dimension of hyperplanes over finite fields <ref:2609. p. 032052#pg13>.

[3] Michael Bennett, Jeremy Chapman, David Covert, Derrick Hart, Alex Iosevich, and Jonathan Pakianathan. Long paths in the distance graph over large subsets of vector spaces over finite fields <ref:2609. p. 032052#pg14>.

[4] Michael Bennett, Derrick Hart, Alex Iosevich, Jonathan Pakianathan, and Misha Rudnev. p. 0 Group actions and geometric combinatorics in Fd q <ref:2609. p. 032052#pg15>.

[5] Moustapha Diallo and Brian McDonald. p. 0 Vc-dimension of salem sets over finite fields. p. 1

[6] David Fitzpatrick, Alex Iosevich, Brian McDonald, and Emmett Wyman. p. 1 The VC-dimension and point configurations in F2 q. p. 0

[7] Christopher Housholder, Layna Mangiapanello, and Steven Senger. VC-dimension of subsets of Hamming graphs. p. 0

[8] A. Iosevich, B. p. 1 McDonald, and M. p. 0 Sun. Dot products in F3 q and the Vapnik-Chervonenkis dimension. p. 0

[9] Alex Iosevich, Akos Magyar, Alex McDonald, and Brian McDonald. p. 0 The VC-dimension and point configurations in R d. p. 0

[10] Serge Lang. Algebra, volume 211 of Graduate Texts in Mathematics. Springer-Verlag, New York, third edition, 2002. p. 0

[11] Brian McDonald, Anurag Sahay and Emmett L. p. 0 Wyman. The VC dimension of quadratic residues in finite fields. p. 0

[12] Brad Rodgers and Anurag Sahay. The VC-Dimension of Random Subsets of Finite Groups. p. 0

[13] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning - From Theory to Algorithms. p. 0

Page 1

VC-DIMENSION OF DISTANCE GRAPHS IN FINITE FIELD GEOMETRIES BRIAN MCDONALD BAKAS, MOUSTAPHA DIALLO, AND ALEX MCDONALD Abstract. We study the VC-dimension of distance graphs of large subsets of vector spaces over finite fields. p. 0

Page 2

BRIAN MCDONALD BAKAS, MOUSTAPHA DIALLO, AND ALEX MCDONALD For t ∈ Fq and d ≥ 2, define the sphere of radius t by Sd−1t = Xd−1t = Xd−1t = Xd−1t = Xd−1t. Finally, for E ⊂ Fdq and t ∈ Fq, the t-distance graph of E is the graph with vertex set E and adjacency relation defined by x ∼ y if and only if x − y = t. p. 1 p. 1

Page 3

VC-DIMENSION OF DISTANCE GRAPHS IN FINITE FIELD GEOMETRIES 3 Figure 1. The graphs S1, S2, S3 (Xk blue, Yk black). p. 2 With these definitions, we see that the VC-dimension of a graph G is at least k if1 G contains Sk as an induced subgraph. p. 2

Page 4

BRIAN MCDONALD BAKAS, MOUSTAPHA DIALLO, AND ALEX MCDONALD For t ∈ Fq and d ≥ 2, define the sphere of radius t by Sd−1t = Xd−1t = Xd−1t = Xd−1t. Finally, for E ⊂ Fdq and t ∈ Fq, the t-distance graph of E is the graph with vertex set E and adjacency relation defined by x ∼ y if and only if x − y = t.

Page 5

VC-DIMENSION OF DISTANCE GRAPHS IN FINITE FIELD GEOMETRIES 5 Definition 1.7. For k ∈ N, let [k] = 1,. p. 0.., k. The k-shattering graph, denoted Sk, is any of the (isomorphic) bipartite graphs with parts Xk = x1,. p. 2.., xk and Yk = yI: I ⊂ [k], where xi ∼ yI if and only if i ∈ I.

Page 6

BRIAN MCDONALD BAKAS, MOUSTAPHA DIALLO, AND ALEX MCDONALD Definition 1.8. Fix E ⊂ Fdq and t ∈ Fqsetminus 0. p. 2 A star is a copy of Kk,1 in Gt(E), which we will denote by (X, y), where X ∈ E k is the k-part and y ∈ E is the 1-part. p. 2

Page 7

VC-DIMENSION OF DISTANCE GRAPHS IN FINITE FIELD GEOMETRIES 7 Definition 1.9. If G is a graph and x is a vertex, recall that N(x) denotes the neighborhood of x. p. 2 If S is a set of vertices, we define NS = [x∈S N(x) and Ne(S) = x∈S Ne(x). p. 2

Page 8

BRIAN MCDONALD BAKAS, MOUSTAPHA DIALLO, AND ALEX MCDONALD When E ⊂ Fdq and t ∈ Fq are fixed, we understand all graph-theoretic notation to refer to the graph Gt(E).

Page 9

VC-DIMENSION OF DISTANCE GRAPHS IN FINITE FIELD GEOMETRIES 9 Definition 1.10. For a set E subset Fdq, let aff(E) denote the maximum number of affinely independent points in E (equivalently, aff(E) − 1 is the dimension of the affine span of E. p. 3

Page 10

BRIAN MCDONALD BAKAS, MOUSTAPHA DIALLO, AND ALEX MCDONALD Theorem 1.11 Let k, r, d, m ∈ N satisfy 3 ≤ k ≤ d, 1 ≤ m ≤ d + 1, 2 ≤ r ≤ d+2/2 and for each 1≤j < k let αj ∈ [0, j]. p. 3 There exists a constant C (depending on k, r, d, m, maxj αj, minj αj) such that the following holds. p. 3 Define s = max d + 1/2, d − r + 1, max j < k d + j + r − 3/2 + j − αj, k − 1. p. 3

Page 11

VC-DIMENSION OF DISTANCE GRAPHS IN FINITE FIELD GEOMETRIES 11 Proof of Theorem 1.4 Let E subset Fdq satisfy (1. p. 83) B ∈ E j: 1 m.

Page 12

BRIAN MCDONALD BAKAS, MOUSTAPHA DIALLO, AND ALEX MCDONALD Proof of Theorem 1.4 Let 2 ≤ r ≤ d+2/2 be an integer parameter to be chosen later. p. 0

Page 13

VC-DIMENSION OF DISTANCE GRAPHS IN FINITE FIELD GEOMETRIES 13 Let r = d−k/3 + 2. Clearly r ≥ 2, and it is easy to check r ≤ d+2/2 provided k ≥ 3. p. 0

Page 14

BRIAN MCDONALD BAKAS, MOUSTAPHA DIALLO, AND ALEX MCDONALD Proof of Corollary 1.5 The claimed exponent s = d−1 follows from taking k = d in Theorem 1. p. 1 p. 14.

Page 15

VC-DIMENSION OF DISTANCE GRAPHS IN FINITE FIELD GEOMETRIES 15 Proof of Corollary 1.6 We apply Theorem 1. p. 7 p. 74 with k = 3.

Page 16

BRIAN MCDONALD BAKAS, MOUSTAPHA DIALLO, AND ALEX MCDONALD Sharpness of Corollary 1.5 The claimed exponent s = d−1 follows from taking k = d in Theorem 1.4.

Page 17

VC-DIMENSION OF DISTANCE GRAPHS IN FINITE FIELD GEOMETRIES 17 Proof of Corollary 1.6 We apply Theorem 1.4 with k = 3.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved complexity analysis for distance graphs in finite field geometries allows AI systems to establish lower bounds on VC-dimension based on set size, specifically that "the distance graph of E subset F d q has VC-dimension at least k provided that E > Cqd−floor(d−k/3)−1" for 3 <= k <= d.

  2. Enhanced capability to guarantee high VC-dimension for distance graphs by leveraging the bound from Corollary 1.5, which states "if E subset F d q satisfy E > Cqd−1, then Gt(E) has VC-dimension at least d for every t in Fq except 0."

  3. Development of a method to determine when the VC-dimension of a distance graph is at least 3 by ensuring the set size exceeds Cqceil(2d/3), which is useful for applications requiring at least three shatterable configurations.

  4. Application of Lemma 3.2, which allows for the creation of subsets E' from a larger set E such that for every x in E' we have deg(x) approx Eq to improve the counting of k-stars and thus prove Theorem 1.11 and Corollary 1.5.

  5. Implementation of a proof strategy showing that "M < At,k(E', E'') by taking C large enough, depending on these parameters," which provides a constructive way to find a k-star that does not admit a bad set for the main theorem proof.

  6. Ability to precisely calculate the required size exponent for Corollary 1.6 by applying Theorem 1.4 with k=3, resulting in s = d - floor(d/3) = ceil(2d/3), which dictates the minimum size of E needed to guarantee VC-dimension at least 3.

  7. Utilization of Theorem 4.3, which states For any t in Fq except 0 there exists a set E subset Fq with E approx qd−1 such that the VC-dimension of Gt(E) is at most d − 1, to bound the complexity of orthogonality graphs O(E) for distance-like structures.

  8. Capability to constrain the VC-dimension of an orthogonality graph O(E) by showing the VC-dimension of O(E) is at most d−1 when E subset F d q minus S d−1 0, which limits the complexity of zero dot product configurations in high dimensions.

Sources

Related papers