### General Information

### 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.

### Coworkers

### Presentations

### Additional Information

My Mentor

Professor James Abello

http://www.mgvis.com/

http://www.mgvis.com/AbelloVitaResearchOct08.html