{'fraction_non_alphanumeric': 0.07431227712684667, 'fraction_numerical': 0.01814824248599083, 'mean_word_length': 3.301561216105177, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Collinear Triple Hypergraphs and the Finite Plane Kakeya Problem

We show that the problem of counting collinear points in a permutation (previously considered by the author and J. Solymosi in"Collinear Points in Permutations", 2005) and the well-known finite plane Kakeya problem are intimately connected. Via counting arguments and by studying the hypergraph of collinear triples we show a new lower bound (5q/14 + O(1)) for the number of collinear triples of a permutation of GF(q) and a new lower bound (q(q + 1)/2 + 5q/14 + O(1)) on the size of the smallest Besicovitch set in GF(q)^2. Several interesting questions about the structure of the collinear triple hypergraph are presented.


Introduction
The Kakeya problem, solved in 1928 by Besicovitch, asks for the smallest subset of R 2 so that a unit-length interval may be continuously rotated 360 • within it. The striking answer is that there are sets of arbitrarily small measure that permit such a "full turn." If one does not require that the interval be continuously rotated, but simply that the set contain a unit interval in every direction, there are even sets of measure zero that do the job. This statement also holds in higher dimensions. Perhaps unsurprisingly, such sets must still be "large," i.e., have Hausdorff (or Minkowski) dimension equal to that of the ambient space. To show this is the case in dimensions higher than two is a very important open problem, with deep connections to additive number theory and harmonic analysis.
In his influential manuscript [4], Wolff describes the "finite field Kakeya problem" and makes a convincing argument that the problems that arise are very similar to those of the analytic setting. The finite field Kakeya problem can be stated as follows. A Besicovitch set in F d q is a subset that contains a line in every direction, i.e., a translate of every line through the origin. What is the smallest Besicovitch set? The natural conjecture is that it has cardinality cq d , but this is not known in dimensions greater than 2. (Indeed, the best result for dimension 3 is only q 5/2+10 −10 [3].) It is easy to see that, for the finite plane, every Besicovitch set has cardinality at least q 2 /2. In fact, this result appears already in [4]. On the other hand, there is a natural construction that gives an upper bound of q(q + 1)/2 + (q − 1)/2 for q odd. Hence, we have the following conjecture.
(The situation when q is a power of two is considerably simpler.) Recently, Faber [2] provided a very elegant argument that, in fact, the smallest finite plane Besicovitch set has cardinality at least q(q + 1)/2 + q/3, getting quite close to the upper bound.
In the current paper, we show that (1) Faber's argument dualizes to improve the best known bound for the number of collinear triples of a permutation (see [1] and the next section); and (2) with some additional work, it is possible to prove the following theorem: Theorem 1. The smallest Besicovitch set in F 2 q has cardinality at least Note that 5/14 = 1/3 + 1/42, so this is indeed an improvement. In fact, this lower bound gives the conjectural upper bound for q = 3, 5, 7, 9. We include below several very interesting problems that arise from our analysis.

Preliminaries
Let q be an odd prime power. Write F q for the finite field of order q and F * q for its multiplicative group, i.e., F q \{0}. Let f : F q → F q be some function; then we define the "graph of f ", denoted Γ f , to be the set {(j, f (j)) : j ∈ F q } ⊂ F 2 q .
We will write m ij = m ij (f ) for the slope of the line connecting the points in Γ f corresponding to the ordinates i and j, i.e., m ij = (f (j)−f (i))/(j −i). We refer to the slope of a collinear set of points in the obvious sense, and call two collinear sets with the same slope "parallel." In general, a slope is an element of P G(1, q), and therefore can take on the value ∞ if the denominator of this expression is 0, although this is clearly never the case for a graph Γ f . Also, the slope of points in Γ σ cannot be 0 for σ a permutation. Finally, we write ℓ(x, m) for the line in F 2 q through x with slope m. Suppose that P is a minimal Besicovitch set in F 2 q . Clearly, we may assume that P is of the form Write µ(y) = |{m ∈ P G(1, q) : y ∈ ℓ(x m , m)}|, i.e., the multiplicity of y in the representation of P by (1). We have the following "incidence formula" for the size of P from [2]: Theorem 2 (Incidence Formula, [2]).
Note that µ(y) The following result (actually, an equivalent version) appears in [2]. For a Besicovitch set P of the form (1), define ρ(m) to be the sum of µ(y)−2 over all y ∈ ℓ(x m , m) with µ(y) ≥ 3.
It is not hard to conclude from this Proposition and Theorem 2 that |P | ≥ q(q + 1)/2 + q/3. We can go further with this result, however. Indeed, suppose that min m∈P G(1,q) ρ(m) = R. If R ≥ 2, then Hence, Theorem 1 follows unless R = 0 or R = 1. Now, we may apply a nonsingular affine transformation of F 2 q to make the line ℓ(x m , m) with ρ(m) = R become the vertical line through the origin while retaining the property of P being a minimal Besicovitch set. Dualizing the nonvertical lines of P under the map {(x, y) : y = mx + b} → (m, b) gives a set S ⊂ F 2 q which is the graph Γ σ of some function σ. If R = 0, then σ is a permutation; if R = 1, then σ is a "semipermutation", that is, a function whose range has cardinality q − 1. If R = 0, points y with µ(y) ≥ 3 correspond to collinear µ(y)-tuples in Γ σ ; if R = 1, then all y with µ(y) ≥ 3 except the single point of multiplicity ≥ 3 on ℓ((0, 0), ∞) correspond to collinear µ(y)-tuples in Γ σ .
This leads us to the following definition. Given S ⊂ F 2 q = F q × F q , define the 3-uniform hypergraph C(S) on the vertex set S to be the set of all collinear triples {x 1 , x 2 , x 3 } ⊂ S. Let L(S) for the hypergraph on the vertex set S whose edges are the maximal collinear subsets of S. For a hypergraph H, write H for the quantity e∈E(H) (|e| − 1)(|e| − 2)/2; we write S = L(S) for convenience. Note that the number of edges in C(S), which we write simply |C(S)|, is at least S . It is clear by the Incidence Formula that, when R = 0 and σ is the permutation arising from dualizing P , When R = 1 and σ is the semipermutation arising from dualizing P , Our problem therefore reduces to that of determining the minimum value of Γ σ when σ is a permutation or a semipermutation. In both cases, we may assume that every point of Γ σ appears in at least one edge of C(Γ σ ) by the minimality of R and Proposition 3. In fact, we reprove this statement below for permutations, since the argument is so short and elegant.
The following conjecture appears in [1], along with a proof of the lower bound (q − 1)/4.

Conjecture 2. For any permutation
If this conjecture is true, it is best possible, as evidenced by the graph of the function s → s −1 for s = 0 and 0 → 0. Unfortunately, we still cannot show the full conjecture. However, we do show below that every permutation σ satisfies Γ σ ≥ (5q − 1)/14, from which it follows that the number of collinear triples in Γ σ is at least this quantity. Furthermore, we show that every semipermutation σ so that C(Γ σ ) has no isolated points satisfies Γ σ ≥ 5(q − 1)/14. In the former case, then, |P | ≥ q(q + 1)/2 + (5q − 1)/14, and in the latter, Theorem 1 follows.

Permutations
Throughout this section we assume that σ : F q → F q is a permutation. The next proposition states that no point of Γ σ is isolated in C(Γ σ ), and the argument is essentially the dual of that appearing in [2].
Proof. Clearly we may assume that (j, σ(j)) = (0, 0). Suppose (j, σ(j)) were an isolated point in Γ σ , i.e., there exists no E ∈ C(Γ σ ) so that (j, σ(j)) ∈ E. Consider the slopes m 0i for i = 0, and, in particular, the product Since (0, 0) does not participate in any collinear triple, the line ℓ((0, 0), m) contains at most two points for each m ∈ F * q (including the origin). However, since there are q − 1 such lines and q − 1 points (j, σ(j)) for j = 0, each such line contains exactly two points of Γ σ , by the pigeonhole principle. This means that M is the product of all elements of F * q , which it is easy to see is −1. On the other hand, In fact, Proposition 4 can be pushed considerably further.
We may assume without loss of generality that x = (0, 0). Consider again the product On the one hand, the numerator and denominator of this expression both enumerate all elements of F * q , so that M = 1. On the other hand, Hence, Call a point p ∈ Γ σ which belongs to exactly one collinear triple "lonely," i.e., |{E ∈ C(Γ σ ) : p ∈ E}| = 1.
Proposition 6. If x = (j, σ) is lonely, then 1. There is one slope m j ∈ F * q so that ℓ(x, m j ) contains three points of Γ σ , one slope m ⊥ j so that ℓ(x, m ⊥ j ) contains one point of Γ σ , and all other slopes m = m j , m ⊥ j are such that ℓ(x, m) contains two points.
Proof. Since x participates in exactly one collinear triple, it is easy to see that, letting m j be the slope of that triple, |ℓ(x, m j ) ∩ Γ σ | = 3 and |ℓ(x, m) ∩ Γ σ | ≤ 2 for all other m ∈ F * q \ {m j }. There are q − 2 other slopes, while there are only q − 3 other points (i, σ(i)). Hence, only q − 3 of the lines ℓ(x, m), m ∈ F * q \ {m j } actually have a point of Γ σ besides x on them, leaving one line with no other point. This slope we call m ⊥ j . To see the second claim, we need only apply the previous proposition with Problem 3. Can an edge of C(Γ σ ) be isolated, i.e., its three points lonely?
If not, then we may conclude that Γ σ ≥ 2q/5 by a simple counting argument. Indeed, we have the following.
Proposition 7. If T ⊂ Γ σ of cardinality t induces no isolated edges and no isolated points in C(Γ σ ), then Proof. Clearly, it suffices to prove a lower bound of 2/5 on the quotient H /t for all connected hypergraphs H on t vertices with at least 2 edges and so that each edge contains at least three points. Note that, for any such H, it is possible to order its edges e 1 , . . . , e k so that each e j , 2 ≤ j ≤ k, intersects e i for some i < j. Define Then a 1 = |e 1 | and a j ≤ |e j | − 1 for j > 1. Since t = k j=1 a j , by Cauchy-Schwarz. Let ǫ = e∈H |e| and h = |H|. Then this reduces to which it is easily checked over h ≥ 2, ǫ ≥ 3h attains its minimum of 2/5 at h = 2, e = 6.
Define an isolated matching of a hypergraph H to be a set of (disjoint) isolated edges, i.e., a matching which is not intersected by any other edges of H.
Lemma 8. For every isolated matching M ⊂ C(Γ σ ), there are at least 2|M|+ t − Γ σ − 1 slopes m ∈ F * q so that there exists an ℓ(x, m) whose intersection with Γ σ consists of exactly one point of T , where t = |T |.
Proof. Suppose that M ⊂ C(Γ σ ) has exactly (q − t)/3 edges, leaving a set T = Γ σ \ M of t other vertices. Let S 1 be the set of slopes of all collinear triples contained in T , so that |S 1 | ≤ T . Note that every edge of C(Γ σ ) containing a point of T in fact contains three points of T , since M is an isolated matching. Consider the set of slopes S 2 which occur in M, or whose negative is an element of M. Then |S 2 | ≤ 2|M| = 2(q − t)/3, and |S 1 ∪ S 2 | ≤ T + 2(q − t)/3. Hence, there exist at least slopes m ∈ F * q which are not elements of S 1 ∪S 2 . Since T = Γ σ −(q−t)/3, this quantity is at least Hence there is an odd number of lines of type (c). Now, for a point x ∈ Γ σ , define x to be the sum over all maximal collinear subsets {y 1 , . . . , y k } ⊂ Γ σ of the quantity φ(k) = (k−1)(k−2)/(2k).
Proof. It is easy to see that, since M is an isolated matching, The conclusion then follows immediately from Lemma 9.

Semipermutations
Throughout this section, we assume that σ is a function from F q to itself which repeats exactly one value, i.e., |σ(F q )| = q − 1, and so that there are no isolated points in C(Γ σ ). Fix the following notation: σ(F q ) = F q \ {b}, σ(z 1 ) = σ(z 2 ) = a for some z 1 , z 2 ∈ F q , z 1 = z 2 .
Proposition 12. If x = (j, σ) is lonely for j = z 1 , z 2 , then 1. There is one slope m j ∈ F * q so that ℓ(x, m j ) contains three points of Γ σ , one slope m ⊥ j so that ℓ(x, m ⊥ j ) contains one point of Γ σ , and all other slopes m = m j , m ⊥ j are such that ℓ(x, m) contains two points.
. Proof. The proof of (1) is identical to that of Proposition 6. To see the second claim, note that On the other hand, the numerator of the left-hand side is given by and the conclusion follows.
Proposition 13. If x = (j, a) is lonely for j = z 1 (or z 2 ), then 1. There is one slope m j ∈ F * q so that ℓ(x, m j ) contains three points of Γ σ , two slopes m ⊥ j1 , m ⊥ j2 so that each ℓ(x, m ⊥ ji ) contains one point of Γ σ , and all other slopes m = m, m ⊥ j1 , m ⊥ j2 are such that ℓ(x, m j ) contains two points.
there is exactly one m j for which |ℓ(x, m j ) ∩ Γ σ | = 3 (since x is lonely), and all other intersections contain 1 or 2 points. Since q − 2 of the points of Γ σ are counted exactly once by these quantities -that is, all of Γ σ except x and (j ′ , a) -we have This, in turn, implies that there are q − 4 slopes m ∈ F * q so that ℓ(x, m j ) ∩ Γ σ consists of exactly two points, and the remaining (q − 1) − (q − 4) − 1 = 2 directions m ⊥ j1 , m ⊥ j2 contain only one point: x. For the second claim, note that On the other hand, the numerator of the left-hand side is given by and the conclusion follows.
Lemma 14. For every isolated matching M ⊂ C(Γ σ ), there are at least 2|M| + t − Γ σ − 3 slopes m ∈ F * q so that there exists an ℓ(x, m) whose intersection with Γ σ consists of exactly one point of T , where t = |T |.
Proof. Suppose that M ⊂ C(Γ σ ) has exactly (q − t)/3 edges, leaving a set T = Γ σ \ M of t other vertices. Let S 1 be the set of slopes of collinear triples in T , so that |S 1 | ≤ T . Note that every edge of C(Γ σ ) containing a point of T in fact contains three points of T , since M is an isolated matching. Consider the set S 2 of slopes m j and m ⊥ j which occur in M. Then |S 2 | ≤ 2|M| = 2(q − t)/3 + 2 (the 2 arising in case z 1 or z 2 ∈ M), and |S 1 ∪ S 2 | ≤ T + 2(q − t)/3 + 2. Hence, there exist at least slopes m ∈ F * q which are not elements of S 1 ∪S 2 . Since T = Γ σ −(q−t)/3, this quantity is at least If a line ℓ of slope m intersects M in a point x, then, since m ∈ S 2 and M is an isolated matching, ℓ cannot contain more than one other point of C(Γ σ ). Furthermore, since −m ∈ S 2 , ℓ contains at least one other point of Γ σ . Now, if a line ℓ of slope m does not intersect M but does intersect T , then it cannot intersect T in three or more points, since m ∈ S 1 . Altogether, this means that every line of slope m intersects Γ σ either (a) nowhere, (b) at two points of M, (c) at one point of T , (d) at two points of T , or (e) at one point of M and one point of T .
The conclusion follows from the observation that the quantities |ℓ(x, m)∩ Γ σ | of types (a),(b),(d), and (e) are even, while q, which is odd, satisfies Hence there is an odd number of lines of type (c).

Proof.
Since M is an isolated matching, The conclusion then follows immediately from Lemma 15, since at most two of the x ∈ T are z 1 or z 2 .
Theorem 17. Γ σ ≥ 5q−5 14 . Proof. Suppose that M ⊂ C(Γ σ ) is a maximal isolated matching. Define T = Γ σ \ M and t = |T |. By Lemma 14, there are at least 2|M|+t− Γ σ −3 distinct lines which intersect T in at least one point. Then, by Corollary 16, T ≥ 2|M|/3 + t/3 − Γ σ /3 − 5/3, from which it follows that As mentioned before, we do not even know if it is possible to have a single isolated edge in C(Γ σ ). Of course, the biggest outstanding problem at this time is closing the remaining q/7 gap both in the minimum number of collinear triples of a permutation and the size of the smallest Besicovitch set in F 2 q .