14
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Not the same question, but at a first reading seems to be related enough so that I want the two questions linked :-) $\endgroup$ Commented Dec 29, 2021 at 18:47
  • 1
    $\begingroup$ Thanks for the bounty. But are you really happy with the answers you got? I would think that more can be said. Not necessarily by me. But, there were relatively few constructions, and the proofs about upper bounds are lacking. Nothing about the even case etc. I could sponsor another round, if you don't object. I'm not sure this is necessarily good for the Pearl Dive, but it could come close. Also, eventual answers can likely be understood by many, as they don't necessarily require deep theory. $\endgroup$ Commented Jan 2, 2022 at 15:27
  • $\begingroup$ The risk is that the problem turns out to be a well studied one. Undoubtedly you tried to find something from existing literature? Or was this just your curiosity :-) $\endgroup$ Commented Jan 2, 2022 at 15:28
  • $\begingroup$ @Jyrki I gave the bounty as after all significantly more was done than what I could think of. If you want feel free to give another round, I could give bounty again if you prove even nicer things, such as covering even $n$. Regarding how studied the problem is, I tried googling "mod 3 Oddtown problems" but did not find anything relevant. $\endgroup$ Commented Jan 2, 2022 at 21:02
  • $\begingroup$ Simillary? math.stackexchange.com/questions/2859673/… $\endgroup$
    – nonuser
    Commented Jan 2, 2022 at 21:33

3 Answers 3

8
+50
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ A prime power $q=p^m\equiv7\pmod{12}$ will do just as well. So $p\equiv7\pmod{12}$ and odd $m$. Work with $\Bbb{F}_q\cup\{\infty\}$. $\endgroup$ Commented Dec 30, 2021 at 6:34
  • $\begingroup$ Brilliant, thank you! How did you come up with (or in what similar contexts have you seen) the idea of considering the set of squares? $\endgroup$ Commented Dec 30, 2021 at 13:33
  • 1
    $\begingroup$ @DesmondMiles Squares make an appearance when constructing binary sequences with good correlation properties and other coding theoretical / combinatorial constructions. It is just one of the recurring tricks. I could not make congruences modulo $3$ to match until I saw Ravi's post :-) $\endgroup$ Commented Dec 30, 2021 at 13:58
  • 3
    $\begingroup$ (+1) Very nice answer! Another sighting of this construction is Putnam 1991 problem B5. $\endgroup$ Commented Dec 30, 2021 at 15:13
8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ In the $m=n$ case it thus follows that $A^TA=2I_n$. Meaning that the number of times, call it $N_i$, the element $i$ appears in a set $F_j$, also satisfies the congruence $N_i\equiv2\pmod3$. Also, any two elements appear together in $N_{ij}\equiv 0\pmod3$ times. $\endgroup$ Commented Dec 30, 2021 at 9:58
7
+500
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Nothing new was posted, so you get the bounty. That's fine. After all, you came up with the idea of adding "dummy" extra points to the design to make the congruences match. I'm a bit disappointed by the low turnout. May be the problem is more difficult than I estimated, and our constructions are actually quite good! $\endgroup$ Commented Jan 13, 2022 at 15:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .