How small can the support of a nontrivial $\mathbb F_p$-cocycle on $C_p$ be?

Question

Let $p$ be a prime, and let $\phi : C_p^n \to \mathbb F_p$ be an $\mathbb F_p$-valued $n$-cocycle on $C_p$ (the cyclic group of order $p$) which is not an $n$-coboundary, i.e. $\phi$ represents a nontrivial element of $H^n(C_p;\mathbb F_p)$. Define the support $\operatorname{supp}(\phi) \subseteq C_p^n$ to be the set of elements $\vec g$ such that $\phi(\vec g) \neq 0$.

Question:

1. What is a good lower bound on the cardinality of $\operatorname{supp}(\phi)$?

2. In particular, is there a lower bound which grows exponentially in $n$? (of course, $p^n$ is an upper bound -- I believe $(p-1)^n$ is also an upper bound; so this part of the question assumes that $p \neq 2$)

Remarks:

• When $n=1$, observe that we have a lower bound of $p-1$, which is optimal.

• When $n=2$, the "canonical" cocycle $\phi_\text{carry}$ which defines the extension $\mathbb F_p \to \mathbb Z / p^2 \to C_p$ via usual carry arithmetic has support of cardinality about $p^2 / 2$. I don't know how tight this is; one might try to play with the fact that, perhaps after multiplying by a scalar, we have $\phi = \phi_\text{carry} + d\psi$ for some function $\psi : C_p \to \mathbb F_p$. In order for $\operatorname{supp}(\phi)$ to be small, it would need to be the case that $d\psi$ vanishes on most of the complement of $\operatorname{supp}(\phi_\text{carry})$ (so that in some sense $\psi$ is close to being a homomorphism) and that $d\psi = -1$ on most of $\operatorname{supp}(\phi_\text{carry})$. This sounds like a promising tension, but I don't know how to leverage it.

• For $n \geq 3$ I don't even know where to start.

• Of course, it would be interesting to know something about how this works for other finite groups / other coefficients. I've chosen the above ones for simplicity. I'm not sure what the best formulation would be in the case where $H^n(G;k)$ is not a cyclic $k$-module.

Answer 1

Here is a bound in the case $n=2$.

Suppose $\phi$ is a cocycle with nontrivial cohomology class and $\phi(x,y)=0$ for at least $(1-\epsilon) p^2$ pairs $x,y$. Then $\epsilon \geq 1/8$.

Proof: Without loss of generality, the class of $\phi$ is the standard generator of $H^2(\mathbb Z/p, \mathbb Z/p)$. It follows that $\phi$ arises from a lift $l \colon \mathbb Z/p \to \mathbb Z/p^2$ where $l(x) \equiv x \mod p$, taking $\phi(x,y) = (l(x+y)-l(x) - l(y))/p$.

So we have $l(x+y) = l(x)+l(y)$ for all but $\epsilon p^2$ pairs $x,y$.

Now fix $a \in \mathbb Z/p$. What is the probability that $$ l(b) + l(a-b) = l(c) + l(a-c)$$ for $b,c$ random?

Well, it is the probability that

$$ l(b) - l(c) - l(b-c) = l (a-c) - l(a-b) - l(b-c)$$

and both pairs $(c,b-c)$ and $(a-b,b-c)$ are uniformly distributed, so both sides vanish with probability $1-\epsilon$ by assumption, so both sides are equal with probability $1 - 2 \epsilon$.

By linearity, it follows that there exists a single $c$ such that $$ l(b) + l(a-b) = l(c) + l(a-c)$$ with probability at least $1-2 \epsilon$. So there exists $f(a)$ such that $$l(b) + l(a-b)=f(a)$$ with probability at least $1-2\epsilon$.

Next let's check that $$f(a) + f(b) = f(a+b).$$

Well, we know for $c,d$ random that we have both $f(a) = l(c) + l(a-c)$ and $f(b) = l(d) + l(b-d)$ with probability at least $1-2 \epsilon$ each, so at least $1-4\epsilon$ together.

We have $l(c) + l(d) = l(c+d)$ and $l(a-c) + l(b-d) = l(a+b-c-d)$ with probability $1-\epsilon$ each, so all four events have probability at least $1-6 \epsilon$ together. In this case, we have

$$ f(a) + f(b) = l(c) + l(a-c) + l(d) + l(b-d) =l (c+d) + l(a+b-c-d) $$ which equals $f(a+b)$ with probability at least $1-2\epsilon$.

So $$f(a) + f(b)= f(a+b)$$ with probability at least $1-8 \epsilon$. If $\epsilon< 1/8$, then both sides are equal with positive probability. But both sides are deterministic, so both sides are equal. Hence $f: \mathbb Z/p \to \mathbb Z/p^2$ is a group homomorphism with $f(x) \equiv x \mod p$. But this is impossible, so $\epsilon \geq 1/8$.

---

Let me explain the connection to computer science. This proof relies on an algorithm which, given a black box that computes the function $l \colon \mathbb Z/p \to \mathbb Z/p^2$, computes the homomorphism $f \colon \mathbb Z/p \to \mathbb Z/p^2$ (i.e. sample $l (b) + l(a-b)$ a large but bounded number of times and take the plurality vote).

The algorithm as stated is not very useful, because its output cannot exist and thus its input does not exist, but a similar algorithm works for general groups (constructed by Blum, Luby, and Rubinfield in their paper Self-testing/correcting with applications to numerical problems).

The advantage of this algorithm is that the input needs only be approximately linear (which means it could fail to be linear on exactly the inputs you care about) whereas the output is exactly linear (and can be calculated, with high probability, on the inputs you care about). Because approximate linearity can be tested by checking enough examples, this allows an untrustworthy source to prove to you the existence of a linear function with certain properties in a short amount of time.