Acyclic matching property in $\mathbb{Z}/p\mathbb{Z}$

Question

Let $B$ be a finite subset of the group $G$ which does not contain the neutral element. For any subset $A$ in $G$ with the same cardinality as $B$, a matching from $A$ to $B$ is defined to be a bijection $f : A \rightarrow B$ such that for any $a \in A$ we have $a + f(a) \notin A$. For any matching $f$ as above, the associated multiplicity function $m_f : G \rightarrow \mathbb{Z}_{\geq 0}$ is defined via the rule: $\forall x \in G$, $m_f(x) = |\{a \in A : a + f(a) = x\}|$. A matching $f : A \rightarrow B$ is called acyclic if for any matching $g: A \rightarrow B$, $m_f = m_g$ implies $f = g$. A group $G$ has the acyclic matching property if for any pair of subsets $A$ and $B$ in $G$ with $|A| = |B|$ and $e \notin B$, there is at least one acyclic matching from $A$ to $B$. It is proved here (Propositions 2.2 and 2.3) that there are infinitely many prime $p$ for which $\mathbb{Z}/p\mathbb{Z}$ does not have the acyclic matching property.

Question: Classify all primes with respect to the acyclic matching property. In particular, can we show that for $p > 5$, $\mathbb{Z}/p\mathbb{Z}$ does not have the acyclic matching property?

Update 1: Some useful numerical experiments are found in this paper, page 17, for $p\leq 19$.

Update 2: In this paper, Alon et al. prove that the additive group $\mathbb{Z}^n$ (and in general, any abelian torsion-free group) possesses the acyclic matching property.

Update 3: Counterexamples usually occurs when $|A|=|B|=\frac{p-1}{2}$ or $\frac{p+1}{2}$.

Update 4: It is proved in this paper (Theorem 3.1) that if $A$ and $B$ are subsets of $\mathbb{Z}/p\mathbb{Z}$ with $|A|=|B|$ and $0\notin B$, then there is always a matching from $A$ to $B$. However, this matching need not be acyclic.

Update 5: For small enough subsets, we can always guarantee the existence of an acyclic matching. In particular, we have the following theorem from this paper:

Theorem: Let $p$ be a prime number and suppose $A$ and $B$ are finite subsets of $\Bbb{Z}/p\Bbb{Z}$ with $0\notin B$ which are of the same size $n.$ If $n\leq\sqrt{\log_2p}-1$, then there exists an acyclic matching $f:A\rightarrow B$.

Update 6: The subset of primes $p$ for which $\mathbb{Z}/p\mathbb{Z}$ does not have the acyclic matching property is at least of density $\frac{7}{24}$.

Answer 1

Using a similar approach to LeechLattice's extended comment, consider $A = G \setminus \{0, 1, 3\}$, $B_1 = G \setminus \{0, 1, 2\}$, $B_5 = G \setminus \{0, 1, 6\}$. Over general (i.e. not necessarily prime-order) $\mathbb{Z} / n\mathbb{Z}$ we can define a generating function $F_n$ in $c_0, c_1, c_3$ in which each monomial is weighted by the number of matchings with the corresponding $m_f$, and in both cases these generating functions have a linear recurrence with characteristic polynomial $x^3 - c_1 c_3 x - c_0 c_3^2$. If we then consider slices of the form $n = 6m+k$ we get a linear recurrence with characteristic polynomial $$x^3 - (2 c_1^3 c_3^3 + 3 c_0^2 c_3^4)x^2 + (c_1^6 c_3^6 - 6 c_0^2 c_1^3 c_3^7 + 3 c_0^4 c_3^8)x - c_0^6 c_3^{12}$$

For $n = 6m+1$ we use $B_1$ with initial terms \begin{eqnarray*}F_7 &=& 2c_0 c_1 c_3^2 \\ F_{13} &=& 4 c_0^3 c_1 c_3^6 + 5c_0 c_1^4 c_3^5 \\ F_{19} &=& 6 c_0^5 c_1 c_3^{10} + 35 c_0^3 c_1^4 c_3^9 + 8c_0 c_1^7 c_3^8\end{eqnarray*}

I claim that $$F_{6m+1} = \sum_{j=1}^m \binom{2m+j-1}{3j-2} c_0^{2m-2j+1} c_1^{3j-2} c_3^{4m-j-1}$$

The three base cases are easily checked, and we get a proof by induction with

\begin{eqnarray*}F_{6m+19} &=& (2 c_1^3 c_3^3 + 3 c_0^2 c_3^4) F_{6m+13} - (c_1^6 c_3^6 - 6 c_0^2 c_1^3 c_3^7 + 3 c_0^4 c_3^8) F_{6m+7} + c_0^6 c_3^{12} F_{6m+1} \\ % &=& (2 c_1^3 c_3^3 + 3 c_0^2 c_3^4) \sum_{j=1}^{m+2} \binom{2m+j+3}{3j-2} c_0^{2m-2j+5} c_1^{3j-2} c_3^{4m-j+7} \\&& - (c_1^6 c_3^6 - 6 c_0^2 c_1^3 c_3^7 + 3 c_0^4 c_3^8) \sum_{j=1}^{m+1} \binom{2m+j+1}{3j-2} c_0^{2m-2j+3} c_1^{3j-2} c_3^{4m-j+3} \\&& + c_0^6 c_3^{12} \sum_{j=1}^m \binom{2m+j-1}{3j-2} c_0^{2m-2j+1} c_1^{3j-2} c_3^{4m-j-1} \\ \end{eqnarray*}

First note that all of the exponents of $c_1$ in the recurrence weights are in $\{0,3,6\}$; then

\begin{eqnarray*}[c_1^{3k-2}]F_{6m+19} &=& 2 \binom{2m+k+2}{3k-5} c_0^{2m-2k+7} c_3^{4m-k+11} + \\&& 3 \binom{2m+k+3}{3k-2} c_0^{2m-2k+7} c_3^{4m-k+11} - \\&& \binom{2m+k-1}{3k-8} c_0^{2m-2k+7} c_3^{4m-k+11} + \\&& 6 \binom{2m+k}{3k-5} c_0^{2m-2k+7} c_3^{4m-k+11} - \\&& 3 \binom{2m+k+1}{3k-2} c_0^{2m-2k+7} c_3^{4m-k+11} + \\&& \binom{2m+k-1}{3k-2} c_0^{2m-2k+7} c_3^{4m-k+11} \\ \end{eqnarray*}

so the exponents of $c_0$ and $c_3$ are as desired and the verification of the binomial identity

$$2 \binom{2m+k+2}{3k-5} + 3 \binom{2m+k+3}{3k-2} - \binom{2m+k-1}{3k-8} + 6 \binom{2m+k}{3k-5} - 3 \binom{2m+k+1}{3k-2} + \binom{2m+k-1}{3k-2} = \binom{2m+k+5}{3k-2}$$

is tedious but straightforward.

Finally, note that an acyclic matching requires a value of $j$ for which $\binom{2m+j-1}{3j-2} = 1$, so either $3j = 2$ or $2j=2m+1$, and neither holds for $j \in \mathbb{N}$. Therefore your question is answered in the affirmative for $p = 6m+1$.

---

For $n = 6m + 5$ we use $B_5$ with initial terms \begin{eqnarray*}F_{11} &=& 3c_0 c_1^5 c_3^2 + 5 c_0^3 c_1^2 c_3^3 \\ F_{17} &=& 6 c_0 c_1^8 c_3^5 + 21 c_0^3 c_1^5 c_3^6 + 14 c_0^5 c_1^2 c_3^7 \\ F_{23} &=& 9 c_0 c_1^{11} c_3^8 + 73 c_0^3 c_1^8 c_3^9 + 112 c_0^5 c_1^5 c_3^{10} + 27 c_0^7 c_1^2 c_3^{11} \end{eqnarray*}

I claim that $$F_{6m+5} = \sum_{j=0}^m \left[ \binom{2m+j+1}{3j+2} + \binom{2m+j}{3j+1} + \binom{2m+j}{3j-1} \right] c_0^{2m-2j+1}c_1^{3j+2}c_3^{4m-j-1}$$

Proof is similar but even more tedious. See appendix.

None of the three binomial coefficients in $\binom{2m+j+1}{3j+2} + \binom{2m+j}{3j+1} + \binom{2m+j}{3j-1}$ can be $1$ for $j \in \mathbb{N}$, and since they are non-negative their sum can likewise never be $1$. Therefore your question is answered in the affirmative also for $p = 6m+5 > 5$, which completes the classification.

---

Appendix

Here's some Sage code to verify the core binomial identity for the $6m+1$ and the $6m+5$ cases:

var('m,j')

def coeffF1(m, j):
    return binomial(2*m+j-1, 3*j-2)

def coeffF5(m, j):
    return binomial(2*m+j+1,3*j+2) + binomial(2*m+j,3*j+1) + binomial(2*m+j,3*j-1)

def proof(coeffFn):
    zero = coeffFn(m+3, j) - 2*coeffFn(m+2, j-1) - 3*coeffFn(m+2, j) + coeffFn(m+1, j-2) - 6*coeffFn(m+1, j-1) + 3*coeffFn(m+1, j) - coeffFn(m,j)
    print(zero)
    print(bool(zero == 0))

proof(coeffF1)
proof(coeffF5)

Answer 2

This is not an answer, but it's too long to be included in the comment section.

Conjecture: For any prime $p \geq 7$, $p \neq 29$, let

$ \begin{equation} A=B= \begin{cases} \{1,2,...,p-5,p-3\} & \text{if } p = 1 \text{ mod } 6\\ \{1,2,...,p-7,p-5\} & \text{if } p = 5 \text{ mod } 6\\ \end{cases} \end{equation}$

then there are no acyclic matchings from $A$ to $B$.

Known:

1. The conjecture is true up to $p=47$.

2. For the case $p=29$, let $A=B=\{1,2,...,20,22\}$. Then there are no acyclic matchings from $A$ to $B$.

Remarks:

Let $G$ be a graph on the vertex set $\{(0,a) : a \in A\} \cup \{(1,b) : b \in B\}$, where two vertices $(0,u)$ and $(1,v)$ are connected iff $u+v \notin A$, and the color of the edge is given by $u+v$. Then every matching $f$ amounts to a perfect matching $M$ on the graph $G$, where every vertex $(0,u)$ is connected with $(1,f(u))$, and the multiplicity function is given by the edges in $M$ colored by a certain color.

The graph $G$ has a periodic structure, so the perfect matchings $M$ can be enumerated by linear recurrences (cf. this question). In this way it may be possible to prove that, for every perfect matching $M$, there exists a different perfect matching $M'$ such that for every color $c$, the number of $c$-colored edges is the same in $M$ and $M'$.

Below are the graphs $G$ corresponding to $p=37$ and $p=41$ respectively.

Update: My conjecture is false for all primes of the form $30n+29$. For such a prime there is exactly one matching with $m_f$ nonzero only at $p-6$ and $p-1$.