Family of sets with $|F_i| \equiv 2\pmod 3$ and $|F_i \cap F_j| \equiv 0 \pmod 3$

Question

Let $p$ be a prime. By considering the incidence vectors of subsets $F_1,\ldots,F_m$ of $\{1,2,\ldots,n\}$, such that $|F_i| = a \not\equiv 0 \pmod p$ and $|F_i \cap F_j| \equiv 0 \pmod p$ for all $1\leq i<j \leq m$, we can show $m\leq n$ (the vectors are linearly independent). For $p=2$ this bound is achievable by the singletons $\{\{1\},\{2\},\ldots,\{n\}\}$, same for $p=3$ with $a=1$. But what about $p=3$ with $a=2$? Is there an example of size $n$ (or perhaps $n - c$ for some "small" constant $c$)?. Observing such examples could help towards ideas of how to improve the bound $m\leq n$ where possible.

Answer 1

An example of size $n-1$ for special values of $n$. Very similar to Ravi's (+1) construction in spirit :-)

Let $p$ be a prime number satisfying the congruence $p\equiv7\pmod{12}$. The field $\Bbb{F}_p$ has $(p+1)/2$ distinct squares, denote their set by $Q$. The translates $$ F_j'=Q+j=\{x^2+j\in\Bbb{F}_p\mid x\in\Bbb{F}_p\} $$ thus also have size $(p+1)/2$ for all $j=0,1,\ldots,p-1$. Because $p\equiv-1\pmod4$ it follows that the intersections $F_j'\cap F_k'$ have exactly $(p+1)/4$ elements whenever $j\neq k$ (ask, if you want an argument).

Here $(p+1)/2\equiv1\pmod3$ and $(p+1)/4\equiv2\pmod3$. So, following Ravi's lead, by tagging on a single shared point, call it $\infty$, we have $p$ subsets $F_j=F_j'\cup\{\infty\}$, $j=0,1,\ldots,p-1$, of the set $\Bbb{F}_p\cup\{\infty\}$ such that $|F_j|\equiv2\pmod3$ and $|F_j\cap F_k|\equiv0\pmod3$ for all $j\neq k$.

---

With $p=7$ (so $n=8$) the squares are $\{0,1,2,4\}$ and the seven sets thus $$\{0,1,2,4,\infty\},\{1,2,3,5,\infty\},\{2,3,4,6,\infty\},\{0,3,4,5,\infty\},\{1,4,5,6,\infty\},\{0,2,5,6,\infty\},\{0,1,3,6,\infty\}.$$ Each with five elements and intersections of size three.

Answer 2

Here's an example of size $n-2$ for some special values of $n$. Let $q \equiv 2 \pmod 3$ be a prime power, $m = q^2 + q + 1$, and $n = m+2$. Identify the ambient set $\{1, \dots, n\}$ with the projective plane over $\mathbb F_q$ plus two extra points $P, Q$. Consider the $m$ subsets of the form $\ell \cup \{P, Q\}$, where $\ell$ is a line in the projective plane. Each of these has cardinality $q + 3 \equiv 2 \pmod 3$. But since distinct lines intersect in cardinality 1, all the pairwise intersections here have cardinality $3$.

Answer 3

From the other direction the following simple argument shows that $m=n$ is impossible, when $n$ is an odd integer.

Assume that we have a construction with $m=n$. Let $A$ be the $n\times n$ matrix with the incidence vector of $F_i$ as its $i$th row. The dictated properties then imply that $$ AA^T=2 I_n $$ in the ring of $n\times n$ matrices over $\Bbb{F}_3$. Here $$2^n=\det(AA^T)=\det(A)^2.$$ But $2^n$ is a square in $\Bbb{F}_3$ if and only if $n$ is even.