MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this community
Let $A$ be a set of cardinality $4n$. We define a pairing in $A$ to be a partition of $A$ into sets of cardinality $2$. What is the minimum number of pairings in $A$ such that every subset of $A$ of cardinality $4$ is the union of two pairs from at least one pairing?
This question is motivated by the computational problem of producing such a set of pairings. An answer may be a proof that the minimum number of pairings with this property is or is not $\mathcal O (n^2)$.
It is a nice exercise in number theory.
Let $p$ be a prime slightly above $4n$. Let $1\le x<y<z<t\le 4n$.
Note that $0<(y+t)-(x+z)<4n<p$.
Now, there exists $a\in \mathbb Z_p$ such that $(x+a)(z+a)=(y+a)(t+a)$ in $\mathbb Z_p$ (this equation only pretends to be quadratic; in fact it is linear in $a$ with non-zero (in $\mathbb Z_p$) coefficient $(y+t)-(x+z)$ at $a$). Also, we cannot have both parts $0$ simultaneously. Thus, if we consider $p^2-p$ pairings $P_{a,b}$ in $\mathbb Z_p\setminus\{-a\}$ given by $u\sim v\Longleftrightarrow (u+a)(v+a)=b$, we will have $x\sim z$ and $y\sim t$ simultaneously for some $a\in\mathbb Z_p, b\in\mathbb Z_p^*$. To reduce $P_{a,b}$ to $[1,4n]$, just make all pairs in $P_{a,b}$ for which both $u,v$ are in the range and then pair the remaining set of numbers of even cardinality in any way you want.
That seems pretty economical. If $N=4n$, then it is essentially $N^2$ while the trivial lower bound is roughly speaking $(N^4/24)/((N/2)^2/2)=N^2/3$. You can try to fight for this $3$, of course, but without me :-)
Let $|A| = N$ (your $4n$). As Fedja observes, the easy lower bound is $\binom{N}{4}/\binom{N/2}{2} \approx N^2/3$, since there are $\binom{N}{4}$ quadruples and each pairing covers $\binom{N/2}{2}$ of them. Fedja gives you a solution that achieves $\approx N^2$. I will do a bit better and get $\approx N^2/2$.
I will explain my solution in the case that $N = p+1$ for $p$ prime; more generally, choose $p$ a little above $N$, use my solution for $p+1$ points, and whenever my solution tells you to pair something in $[1,N]$ with something in $[N+1, p+1]$, choose some arbitrary alternate pairing instead.
First, I'll present Fedja's solution in a more sophisticated way. There are $p^2-p$ involutions in the group $\text{PGL}_2(\mathbb{F}_p)$. In terms of matrices, we are looking at matrices $\left[ \begin{smallmatrix} a&b \\ c&-a \end{smallmatrix} \right]$ where the determinant $a^2+bc$ is nonzero. These involutions act on the projective line $\mathbb{P}^1(\mathbb{F}_p)$ by Mobius transformations: $z \mapsto \tfrac{az+b}{cz-a}$.
For any $4$ distinct elements $(u,v,w,x)$ in $\mathbb{P}^1(\mathbb{F}_p)$, there is an involution with $\text{PGL}_2(\mathbb{F}_p)$ which acts by $u \leftrightarrow v$, $w \leftrightarrow x$. Fedja takes the pairings given by the action of these involution. (I suppose, if he were being careful, he should note that many of these involutions have two fixed points; if so, pair off the fixed points and the solution still works.)
So, I'll do a little better. There are two conjugacy classes of involutions: Those whose determinant is square, and those where the determinant is not square. Each conjugacy class contains $p(p-1)/2$ elements. The upshot of this argument will be that just using the conjugacy class with square determinant is enough, saving a factor of $2$ over Fedja.
For any ordered quadruple $(u,v,w,x)$, let $\rho$, $\sigma$ and $\tau$ be the involutions switching the three pairings of this quadruple. Then $\rho \sigma \tau$ fixes $(u,v,w,x)$, so it is $c \text{Id}$ for some scalar $c$, and $$\det(\rho) \det(\sigma) \det(\tau) = c^2.$$ Thus, an odd number of these involutions have square determinant. This, just using the conjugacy class with square determinant is enough.
