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

  • 2
    $\begingroup$ 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? $\endgroup$
    – KhashF
    Jan 26 at 2:09
  • $\begingroup$ @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. $\endgroup$ Jan 26 at 2:38
  • $\begingroup$ 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. $\endgroup$ Jan 26 at 13:04
  • $\begingroup$ "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? $\endgroup$
    – Stef
    Jan 26 at 15:45
  • 1
    $\begingroup$ The question is reminiscent of the existence of resolvable block designs, but unfortunately I don't see a direct connection. $\endgroup$ Jan 27 at 23:01

2 Answers 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.

  • 1
    $\begingroup$ "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! :-) $\endgroup$
    – fedja
    Jan 26 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.