# Problems with interesting, non-trivial analogues in finite fields

I am wondering what problems* have interesting and non-trivial analogues to finite fields. For example, the Kakeya needle problem, which is usually stated in $$\mathbb{R}^n$$, can be asked in $$\mathbb{F}_q^n$$ with delightful results.

Kakeya Conjecture. The Kakeya Conjecture asserts that every set in $$\mathbb{R}^n$$ which contains a unit line segment in every direction has Hausdorff and Minkowski dimension $$n$$; this has been proven only for $$n=1,2$$. What about in $$\mathbb{F}_q^n$$? Rather than ask about dimension, we should ask for the minimum size of subset of $$\mathbb{F}_q^n$$ that contains a line in every direction; and it turns out this number is bounded below by $$C_nq^n$$, where $$C_n$$ is a constant dependent only on $$n$$.

*I use 'problems' as a shortening of 'problems, conjectures, theorems, etc.' for a more concise title; but I am interested in all of the above.

The classification of simple Lie groups over $$\mathbb R$$ and $$\mathbb C$$ (Killing / Cartan) predated and, at least partly, inspired the classification of finite simple groups, which, at least to a great part, is made up of simple groups of Lie type over finite fields (Chevalley, Steinberg, Tits, Suzuki / Ree ...). Of course now it's exactly the ones that are not of Lie type which often get the limelight, but still ...

The Weil's conjectures can be seen as an analogue of the Riemann hypothesis for finite fields.

• ... and, unlike the Riemann hypothesis, have been proven! – Torsten Schoeneberg Oct 14 at 2:20

Progression-free sets / capsets is a classical example. The original problem, evidently posed by Roth, is to estimate the largest size of a subset of the interval $$[1,N]$$ free of three-term arithmetic progressions. It turned out later that an equally interesting problem emerges if $$[1,N]$$ is replaced with $$\mathbb F_q^n$$.

Fourier analysis was introduced (by Forier) around year 1800. Much later, it was realized that one can do Fourier analysis on any finite group (and many infinite groups, too).

Yet another example: Freiman's structure theorem (around year 1960) describes the structure of sets of integers with $$|2A|. Extensions of this theorem onto arbitrary groups become a powerful tool in additive combinatorics.

Finally, a reference: check out Green's "Finite field models in additive combinatorics" for more examples and discussion.

• can u change "equally interesting"? that's nonsense – mathworker21 Oct 9 at 22:50

– Affine and projective planes over finite fields are useful for a construction of Steiner systems.

This question, asked more than five years ago, turned out to be so deep that we are writing a paper, providing partial answers to it.

There is a special case of the group $$X$$ equal to a Tychonoff power $$\mathbb F^\omega$$ of a finite field $$\mathbb F$$. In this case a dense subgroup $$H$$ of $$\mathbb F^\omega$$ is characteristic iff there exists a linear $$\mathbb F$$-predictor predicting all elements of $$H$$.

We recall that given a filed $$\mathbb F$$, a linear $$\mathbb F$$-predictor is a pair $$\pi=(D,(\pi_k)_{k\in D})$$ consisting of an infinite subset $$D\subseteq \omega$$ and a sequence $$(\pi_k)_{k\in D}$$ of $$\mathbb F$$-linear maps $$\pi_k:\bigoplus_{i=0}^{k-1}\mathbb F\to\mathbb F$$. We say that $$\pi$$ predicts $$x=(x_k)\in\mathbb F^\omega$$ if $$\pi_k(x_0,\dots, x_{k-1})=x_{k}$$ for all but finitely many $$k\in D$$; otherwise $$x$$ evades $$\pi$$, see [Bre] and [Bla, §10]. Let $$\mathfrak e_{\mathbb F}$$ be the smallest size of a set $$E\subseteq\mathbb F^\omega$$ such that every linear $$\mathbb F$$-predictor is evaded by an element of $$E$$.

So we are interested in values $$\mathfrak e_{\mathbb F}$$ for finite $$\mathbb F$$, but this case is different from the case of the infinite $$\mathbb F$$, and a little is known about them. Namely, $$\mathfrak e_{\mathbb F}\ge \operatorname{add} (\mathcal N)$$, where $$\operatorname{add}(\mathcal N)$$ is the smallest number of sets of Lebesgue measure zero, covering the real line and it is consistent that $$\mathfrak e_{\mathbb F} > \mathfrak b, \mathfrak e, \mathfrak s$$, see [Bre, Section 4]. The cardinals $$\mathfrak b$$, $$\mathfrak e$$, and $$\mathfrak s$$ are called small, because they are placed between $$\omega_1$$ and $$\frak c$$ (see, in particular, [Dou, Theorem 3.1]). Recall (see, for instance, [Dou, §3]) that $$\mathfrak b$$ is the smallest size of a family $$\mathcal F$$ of functions from $$\omega$$ to $$\omega$$ such that there is no funciton $$g$$ from $$\omega$$ to $$\omega$$ such that for each $$f\in\mathcal F$$, we have $$g(n)\ge f(n)$$ for all but finitely many $$n$$. The cardinal $$\mathfrak s$$ is the smallest size of a family $$\mathcal G$$ of infinite subsets of $$\omega$$ such that for each infinite subset $$C$$ of $$\omega$$ exists a set $$S\in\mathcal G$$ such that both sets $$C\cap S$$ and $$C\setminus S$$ are infinite. The cardinal $$\mathfrak e$$ is a (non-linear) evading number for a countably infinite set, see [Bla, §10] or [Bre].

References

[BR] Alex Ravsky, Taras Banakh, A note on $$\mathfrak g$$-dense subgroups of compact Abelian topological groups, in preparation.

[Bla] A. Blass, Combinatorial Cardinal Characteristics of the Continuum, in: M. Foreman, A. Kanamori (eds.), Handbook of Set Theory, Springer Science+Business Media B.V. 2010, 395--489.

[Bre] Jörg Brendle, Evasion and prediction – the Specker phenomenon and Gross spaces, Forum Math. 7 (1995), 513--541.

[Dou] E.K. van Douwen, The Integers and Topology, in K. Kunen, J. E. Vaughan (eds.), Handbook of Set-Theoretic Topology, Elsevier, 1984, 111--167.

The theory of group representations seeks to describe group elements as linear transformations of vector spaces. In the first instance, these were vector spaces over the field of complex numbers, but nowadays vector spaces over finite fields are of similar prominence.