# Minimum number of pairings that make all quadruples

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

• Let $\mathcal{P}$ be a subset of pairings. Do you want a lower bound for $|\mathcal{P}|$ when $\mathcal{P}$ satisfies the property you want or you mean a lower bound that guarantees $\mathcal{P}$ has that property? Jan 26 at 2:09
• @KhashF: The practical problem is to generate a set of pairings $\mathcal P$ that is small and that does have the property. The mathematical problem is to find such a set $\mathcal P$ that minimizes $|\mathcal P|$, but perhaps only asymptotically. Jan 26 at 2:38
• Here is an idea which I don't have time to follow up on: For $a<b<c<d$, there are three pairings of $\{ a,b,c,d \}$: The disjoint pairing $(ab, cd)$, the crossing pairing $(ac, bd)$ and the matching pairing $(ad, bc)$. One could wonder how many pairings on $[N]$ are necessary in order to include (a) all the disjoint pairings (b) all the crossing pairings or (c) all the matching pairings. Since we have naturally divided the pairings into 3 types, one could imagine seeing the optimal factor of 1/3 by organizing them this way. Jan 26 at 13:04
• "Since we have naturally divided the pairings into 3 types" Well, only for a set of 4 elements. How would you extend this partition for larger sets?
– Stef
Jan 26 at 15:45
• The question is reminiscent of the existence of resolvable block designs, but unfortunately I don't see a direct connection. Jan 27 at 23:01

It is a nice exercise in number theory.

Let $$p$$ be a prime slightly above $$4n$$. Let $$1\le x.

Note that $$0<(y+t)-(x+z)<4n.

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.

• "he should note that many of these involutions have two fixed points" Indeed :-) I just didn't care: the point was that one doesn't get any number paired with several ones in a single pairing and that one can split any 4-set in $[1,N]$ into two 2-sets that are paired in some pairing of $\mathbb F_p$, even if that pairing is only partial (which, as you noted, it is). So, coming back to my low-tech language, you are saying that I needed to take special care of the case with two equal sums (pairing by the sum) and then could restrict to $b$ such that $-b$ is a quadratic residue? Beautiful! :-) Jan 26 at 12:28