### General Information

Student: Karel Král 444 Charles University in Prague kralka guess_what_is_here kam.mff.cuni.cz Binary Kakeya Sets DIMACS REU 2013

### Project Description

For $x,y \in \{0,1\}^n$ we define the line $L_{x,y} = \{x^i \oplus y \mid i = 0, ..., n-1\}$ of direction $x$ where $x^i$ denotes the $i$-th rotation of $x$. We say that a set $S \subseteq \{0,1\}^n$ is a Kakeya set if for every $x \in \{0,1\}^n$ there exists $y \in \{0,1\}^n$ such that $L_{x,y} \subseteq S$. Michal Koucký asks for the smallest Kakeya set for a given $n$.

### Previous Work

• J. Bourgain Harmonic analysis and combinatorics: How much may they contribute to each other? IMU/Amer. Math. Soc., pages 13–32, 2000.
• Zeev Dvir On the size of Kakeya sets in finite fields, arXiv:0803.2336 [math.CO].

### Weekly Log

#### First Week

• We got the problem.
• Reading the article by Zeev Dvir.
• Few first observations.
• First rather trivial upper bound.

#### Second Week

• We managed to get a slightly better upper bound of roughly $2^{n-1}(1-1/n)$.
• Running computer experiments by Peter.
• Trying to make some progress by observing smaller cases.
• More small observations.

#### Third Week

• Trying other ideas for computer experiments.
• Trying to get some insight using a greedy algorithm.
• Greedy algorithm gives nearly optimal solutions for small values of $n$. Depending on the order of added lines.
• We know sizes of smallest Kakeya sets for $n \leq 6$.

#### Fourth Week

• Nontrivial lower bound! (With corrected proof.) Roughly $2^{n/2}$.
• Another observation about sizes of Kakeya sets.
• For a Kakeya set there is always a point such that its neighbors are all cointained in the given Kakeya set.
• We have that $K_n \leq K_{2n + \ell}$ for every $\ell \geq 0$.

#### Fifth Week

• Writing a summary of what we did and what we proved. Might be useful for the final report.
• Trying new ideas how to use polynomial method and how to represent binary strings in a different way.
• Searching for a construction of a Kakeya set of dimension $n$ from a smaller Kakeya set of dimension $m < n$.
• Trying to get a better bound of the type $K_n \leq K_{2n}$ from the last week.

#### Sixth Week

• We think that it is enough to select $y$ just from the set of basic vectors (10000, 01000, 00100, etc.).
• A bit better lower bound for prime numbers.
• We conjecture that the size of $\cup L_{x^i x}$ is the same for all $n>7$ primes.
• Tight upper bound for the previous conjecture.

#### Seventh Week

• Prepairing final presentation.
• Writing final report.
• Trying to prove some conjectures from the last week.
• Leaving to Prague on Friday.