A General Framework for Low Soundness Homomorphism Testing

Mittal, Tushant; Roy, Sourya

doi:10.4230/LIPIcs.ITCS.2026.103

A General Framework for Low Soundness Homomorphism Testing

Tushant Mittal

Stanford University, CA, USA Sourya Roy

University of Iowa, Iowa City, IA, USA

Abstract

We introduce a general framework to design and analyze algorithms for the problem of testing homomorphisms between finite groups in the low-soundness regime.

In this regime, we give the first constant-query tests for various families of groups. These include tests for: (i) homomorphisms between arbitrary cyclic groups, (ii) homomorphisms between any finite group and ${\mathbb{Z}}_{p}$ , (iii) automorphisms of dihedral and symmetric groups, (iv) inner automorphisms of non-abelian finite simple groups and extraspecial groups, and (v) testing linear characters of $\mathrm{GL}_{n}({\mathbb{F}}_{q})$ , and finite-dimensional Lie algebras over ${\mathbb{F}}_{q}$ . We also recover the result of Kiwi [TCS’03] for testing homomorphisms between ${\mathbb{F}}_{q}^{n}$ and ${\mathbb{F}}_{q}$ .

Prior to this work, such tests were only known for abelian groups with a constant maximal order (such as ${\mathbb{F}}_{q}^{n}$ ). No tests were known for non-abelian groups.

As an additional corollary, our framework gives combinatorial list decoding bounds for cyclic groups with list size dependence of $O(\varepsilon^{-2})$ (for agreement parameter $\varepsilon$ ). This improves upon the currently best-known bound of $O(\varepsilon^{-105})$ due to Dinur, Grigorescu, Kopparty, and Sudan [STOC’08], and Guo and Sudan [RANDOM’14].

Keywords and phrases:

Property Testing, Coding Theory

Funding:

Tushant Mittal: T.M. is a postdoctoral fellow supported by the NSF grants CCF-2143246 and CCF-2133154.

Sourya Roy: S.R. was partially supported by the Old Gold Summer Fellowship from The University of Iowa.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Error-correcting codes

Related Version:

Full Version: https://arxiv.org/abs/2509.05871

Acknowledgements:

We sincerely thank the reviewer for their helpful comments and careful reading of our manuscript.

DOI:

10.4230/LIPIcs.ITCS.2026.103

Event:

17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Editor:

Shubhangi Saraf

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The problem of homomorphism testing has been extensively studied in the theoretical computer science literature [2, 6, 17, 23, 15]. A primary motivation for studying this question is its relevance to the theory of probabilistically checkable proofs [4, 5] and locally testable codes. Additionally, there has been an interest in studying such tests in quantum complexity, for example, entanglement testing [20] involves homomorphism testing which played an important role in the proof of $\mathrm{MIP}^{*}\text{=}\mathrm{RE}$ [16].

In this work, we study this homomorphism testing problem in the context of general finite groups. To make the discussion precise, we begin by formally describing the setup. Let $G$ and $H$ be two finite groups. Denote by $\textup{Hom}(G,H)$ , the set of all homomorphisms from $G$ to $H$ , i.e., a function such that, $f(xy)=f(x)\cdot f(y)$ for each $x,y\in G$ .

Definition 1.

$\textup{Hom}(G,H)$ is $(k,\delta,\varepsilon)$ -testable if there exists an algorithm (test) that, given oracle access to a function $f:G\rightarrow H$ , makes $k$ queries to it, and satisfies the following:

$\blacksquare$

(Completeness) If $f$ is a homomorphism, the test passes with probability $1$ .
$\blacksquare$

(Soundness) If test passes with probability $\delta$ (over the choice of queries), then there exists a homomorphism $\varphi$ such that $\operatorname{agr}(f,\varphi)\nobreak\ :=\nobreak\ \mathchoice{\underset{x\sim G% }{\mathrm{Pr}}\left[f(x)=\varphi(x)\right]}{{\mathrm{Pr}}_{x\sim G}[f(x)=% \varphi(x)]}{{\mathrm{Pr}}_{x\sim G}[f(x)=\varphi(x)]}{{\mathrm{Pr}}_{x\sim G}% [f(x)=\varphi(x)]}\nobreak\ \geq\nobreak\ \varepsilon(\delta)$ .

As an example, the famous Blum–Luby–Rubinfield [6] (BLR) test samples a random pair $x,y\sim G$ and checks if $f(x)\cdot f(y)=f(xy)$ . This test shows that $\textup{Hom}({\mathbb{F}}_{2}^{n},{\mathbb{F}}_{2})$ , also known as the Hadamard code, is $\lparen 3,\delta,\delta\rparen$ -testable. We are interested in identifying finite groups, $(G,H)$ , for which the set $\textup{Hom}(G,H)$ is testable and designing such tests.

High Soundness Regime

It is much easier to construct a test that only guarantees soundness when a function passes the test with a probability much larger than the test passing probability of a random function. This regime is known as the high soundness or the unique decoding regime, as there is often a unique homomorphism that agrees with the input function. There are many results in this regime and in particular, Ben Or-Coppersmith-Luby-Rubinfeld [3], showed that $\textup{Hom}(G,H)$ is $(3,\delta,1-\frac{\delta}{2})$ -testable for $\delta>\frac{7}{9}$ for any finite groups $G, H$ . Moreover, the test is the same as the BLR test.

Low Soundness Regime

It is significantly more difficult to design and analyze tests in the low soundness (list decoding) setting when the test passing probability can be arbitrarily small, and the function has a tiny agreement with many homomorphisms. As a sharp contrast to the result of [3], the only known cases for which the BLR test has been analyzed in this low soundness setting are: (i) $({\mathbb{F}}_{p}^{n},{\mathbb{F}}_{p})$ for some prime $p$ , by Håstad and Wigderson [15], and (ii) $({\mathbb{F}}_{p}^{n},{\mathbb{F}}_{p}^{m})$ by Samrodnitsky¹¹1For $p=2$ , this setting is equivalent to the Freiman-Rusza conjecture for which improved bounds were proven in the breakthrough works of [24, 11]. [23] which can be generalized to the setting of $G={\mathbb{Z}}_{p}^{n_{1}}\oplus\dots\oplus{\mathbb{Z}}_{p^{r}}^{n_{r}}$ , where $r=O(1)$ .

Issues with BLR

The high-soundness result of [3] cannot be hoped to generalized to the low soundness setting, as they also give the following counterexample: for any $r\geq 3$ , there exists a function $f:{\mathbb{Z}}_{3^{r}}\rightarrow{\mathbb{Z}}_{3^{r-1}}$ that passes the BLR test with probability $\frac{7}{9}$ but agrees with any homomorphism at most $3^{-(r-1)}$ -fraction of points. This demonstrates that BLR fails catastrophically, even for cyclic groups, in the low-soundness regime.

Moreover, even in cases for which BLR works, it is not always known to yield the best agreement guarantee. For instance, [15] showed that the BLR test for $({\mathbb{F}}_{p}^{n},{\mathbb{F}}_{p})$ achieves an agreement guarantee of $\varepsilon(\delta)=\frac{1+\delta}{p}$ . Hence, even when the function passes with probability $1$ , the guarantee is small for large $p$ . This was remedied by Kiwi [17] by giving a different test²²2Grigorescu, Kopparty and Sudan [13], and Gopalan [10] gave an alternate Fourier analytic proof of Kiwi’s result. which showed that $\textup{Hom}({\mathbb{F}}_{q}^{n},{\mathbb{F}}_{q})$ is $(3,\delta,\delta)$ -testable.

The above discussion shows that new tests and techniques must be devised to handle new families of groups and/or obtain optimal parameters. Additionally, it is desirable to have tests that can provide an improved soundness guarantee by using more queries.

1.1 Our Contribution

We take a first step towards this by defining a general testing framework and using it to get testability results for a variety of groups. In particular, we give the first tests for classes of non-abelian groups in the low-soundness setting. Our meta-test is the following. Let $G, H$ be finite groups, $k$ be an integer, and let $\mathcal{D}_{k}$ be a distribution on $G^{k}$ .

${\sf Test}_{k}(G,H,\mathcal{D}_{k})$

$\blacksquare$

Sample $(x_{1},\dots,x_{k})\sim\mathcal{D}_{k}\subseteq G^{k}$ .
$\blacksquare$

Return $1$ if and only if there exists³³3For almost all the groups we study, there is a simple and efficient way to check this. a homomorphism (or automorphism) $\varphi$ such that $f(x_{i})=\varphi(x_{i})$ for $i\in[k]$ .

We explain the framework in Section 1.2, but briefly summarize its salient features:

$\blacksquare$

Defining the Distribution $\mathcal{D}_{k}$ – A key feature of the framework is that this distribution naturally emerges from an (approximating) expression for the soundness, i.e., $\max_{\varphi\in\textup{Hom}(G,H)}\operatorname{agr}(f,\varphi)$ . The BLR test uses the uniform distribution over $\{(x_{1},x_{2},x_{3})\mid x_{1}x_{2}x_{3}=1\}$ as $\mathcal{D}_{k}$ , regardless of the groups $G, H$ . In contrast, our distribution takes into account the group-theoretic data. In the special case of $({\mathbb{F}}_{2}^{n},{\mathbb{F}}_{2})$ , our distribution coincides with the one in BLR, but for other groups, they are quite different. For example, in the case of cyclic groups, our distribution (roughly) weighs elements based on their order and is not uniform. This difference intuitively explains why BLR fails for cyclic groups, but our test works.
$\blacksquare$

Distance Approximation and List Decoding – Our analysis works by giving an exact expression for the $k^{\mathrm{th}}$ -moment, $\sum_{\varphi}\operatorname{agr}{(f,\varphi)}^{k}$ . This can be seen as a “degree- $k$ variant” of the general Johnson bound (which is for $k=2$ ). Such an expression not only yields a soundness guarantee but also implies a bound on (i) the number of “large-agreement homomorphisms”, i.e., combinatorial list size bounds for homomorphism codes, and (ii) the largest possible agreement that gives a tight control on the distance of the input function $f$ to the property of being a homomorphism. This task of distance approximation was introduced in [22], where they show that approximating distance implies tolerant tests.
$\blacksquare$

Avoiding Fourier Analysis – Our technique works entirely in the “physical space” by reducing the soundness analysis to the computation of certain group-theoretic constants. For some classes of groups (such as finite simple groups), these constants have been studied in the literature. This is helpful when the target group $H$ does not embed easily into ${\mathbb{C}}$ , and one cannot directly rely on Fourier analysis.
$\blacksquare$

Query vs Soundness Tradeoff – The above test works for any (large enough) number of queries $k$ , and the analysis shows that the test guarantee improves exponentially with the number of queries, $\varepsilon(\delta)\approx\delta^{\frac{1}{k}}$ , giving us a smooth tradeoff between query complexity and the soundness guarantee.

1.1.1 Homomorphism Testing

We now summarize our results for homomorphism testing over various classes of finite abelian groups. To the best of our knowledge, all the tests here are novel except for the $3$ -query test for $\textup{Hom}({\mathbb{F}}_{q}^{n},{\mathbb{F}}_{q})$ due to [17].

Theorem 2 (Summary of Homomorphism Testing).

For each pair of groups $G, H$ as listed in Table 1, and correspondingly allowed integers $k$ , $\textup{Hom}(G,H)$ is $(k,\delta,\varepsilon(\delta))$ -testable. The test is ${\sf Test}_{k}(G,H,\mathcal{D}_{k})$ , for an explicitly defined distribution $\mathcal{D}_{k}$ on $G^{k}$ . Additionally, we also get an upper bound of $\max_{\varphi}\operatorname{agr}{(f,\varphi)}\leq O(\delta^{\frac{1}{k}})$ , for any appropriate $k$ as in the table.

Table 1: A summary of our results on homomorphism testing.

Result	$G$	$H$	Query	Soundness $[\varepsilon(\delta)]$
Theorem 27	${\mathbb{F}}_{q}^{n}$	${\mathbb{F}}_{q}$	Odd $k\geq 3$	${\frac{1}{q}-O(\frac{1}{q^{n}})+\lparen\frac{q-1}{q}\rparen\cdot\big\lparen% \frac{q\delta-1}{q-1}\big\rparen^{\frac{1}{k-2}}}$
[17]	${\mathbb{F}}_{q}^{n}$	${\mathbb{F}}_{q}$	$k=3$
Theorem 20	${\mathbb{Z}}_{n}$	${\mathbb{Z}}_{m}$	Any $k\geq 4$	$\big\lparen\zeta(2)^{2}\cdot\delta\big\rparen^{\frac{1}{k-3}}$
Theorem 30	${\mathbb{F}}_{q}$	${\mathbb{F}}_{q}^{n}$	Any $k\geq 2$	$\frac{q-1}{q}\cdot\delta^{\frac{1}{k-1}}$
Theorem 15	${\mathbb{Z}}_{p^{r}}$	Abelian group of $p$ -rank $\leq t$	Any $k\geq t+2$	$\Big\lparen\frac{(p-1)^{2}}{p^{2}}\cdot\delta\Big\rparen^{\frac{1}{k-t-1}}$

Note: The $p$ -rank of an Abelian group is the number of cyclic groups of order a power of $p$ in its decomposition, see Fact 7.

Combinatorial List Decoding

While the focus of our work is not list decoding, our technique yields stronger bounds than currently known for some groups. This is because our analysis gives bounds on $\sum_{\varphi}\operatorname{agr}(f,\varphi)^{k}$ , and the list size then immediately follows.

The work of Dinur, Grigorescu, Kopparty, and Sudan [8], and later Guo and Sudan [14] gave a list size bound of $O\big\lparen\varepsilon^{-105}\big\rparen$ that works for every pair of abelian groups (and in fact “supersolvable” groups). However, their bound does not improve even when $H$ is cyclic. We prove a much better bound of $\varepsilon^{-2}$ for cyclic groups of prime power and $\varepsilon^{-3}$ for general cyclic groups.

Theorem 3 (List Decoding for Cyclic groups).

Let $G={\mathbb{Z}}_{p^{r}}$ and $H={\mathbb{Z}}_{p^{s}}$ be cyclic groups. Let $f:G\rightarrow H$ be any function. Then the following holds:

\big\lvert\{\varphi\in\textup{Hom}(G,H)\nobreak\ :\nobreak\ \operatorname{agr}% (f,\varphi)\nobreak\ \geq\nobreak\ \varepsilon\}\big\rvert\nobreak\ \leq% \nobreak\ \Big\lparen\frac{p}{p-1}\Big\rparen\cdot\frac{1}{\varepsilon^{2}}.

In general, we get a list size bound of ${2\varepsilon^{-(t+1)}}$ when $H$ is an abelian group of $p$ -rank $t\geq 1$ . Additionally, for any integers $n,m\geq 1$ , we get the following list size bound:

\big\lvert\{\varphi\in\textup{Hom}({\mathbb{Z}}_{n},{\mathbb{Z}}_{m})\nobreak% \ :\nobreak\ \operatorname{agr}(f,\varphi)\nobreak\ \geq\nobreak\ \varepsilon% \}\big\rvert\nobreak\ \leq\nobreak\ \frac{\zeta(2)^{2}}{\varepsilon^{3}}\;,

where $\zeta(2)=\frac{\pi^{2}}{6}$ , is the Riemmann-Zeta function.

1.1.2 Automorphism Testing over Non-Abelian Groups

A very important class of homomorphisms arises from automorphisms of groups. Our next set of results concern testing automorphisms and inner automorphisms over various families for finite non-abelian groups. We quickly recall the relevant definitions,

	$\displaystyle\textup{Aut}(G)\nobreak\$	$\displaystyle=\nobreak\ \{\varphi\in\textup{Hom}(G,G)\mid\varphi\;\text{is % bijective}\},$
	$\displaystyle\textup{Inn}(G)\nobreak\$	$\displaystyle=\nobreak\ \{\varphi_{g},\;g\in G\mid\varphi_{g}(x)=gxg\raisebox{% 3.44444pt}{$\scriptscriptstyle-1$}\}\nobreak\ \subseteq\nobreak\ \textup{Aut}(% G).$

The set of inner automorphisms is easier to work with as the maps are very explicit. Moreover, for many groups, the inner automorphisms capture most of the automorphisms. For example, for the symmetric group $\textup{Sym}_{n}$ , all the automorphisms are inner ([25]) (for $n\neq 6$ ). The following theorem consolidates all our automorphism testing results.

Theorem 4 (Automorphism Testing (Summary of Theorems 31 and 32)).

The following results hold by using ${\sf Test}_{k}(G,G,\mathcal{D}_{k})$ for an explicitly defined distribution $\mathcal{D}_{k}$ on $G^{k}$ :

$\blacksquare$

For the family of dihedral groups, $D_{2p}$ ( $p$ prime), $\textup{Aut}(D_{2p})$ is $\Big\lparen k,\,\delta,\,\frac{1}{2}\delta^{\frac{1}{k-2}}\Big\rparen$ -testable for every $k\geq 3$ .
$\blacksquare$

For the family of symmetric groups, $\textup{Aut}(\textup{Sym}_{n})=\textup{Inn}(\textup{Sym}_{n})$ is $\Big\lparen k,\,\delta,\,\delta^{\frac{1}{k-2}}-o_{n}(1)\Big\rparen$ -testable for every $k\geq 3$ , and $n\neq 6$ .
$\blacksquare$

For every non-abelian finite simple group $G$ , $\textup{Inn}(G)$ is $\Big\lparen k,\,\delta,\,\delta^{\frac{1}{k-2}}-o_{|G|}(1)\Big\rparen$ -testable for every $k\geq 4$ .
$\blacksquare$

For any extraspecial group $G$ of order $p^{r}$ , $\textup{Inn}(G)$ is $\Big\lparen k,\,\delta,\,\delta^{\frac{1}{k-r}}-o_{p}(1)\Big\rparen$ -testable for every $k\geq r+1$ . In particular, for the family of Heisenberg groups ( $H_{p}$ ) (the group of $3\times 3$ unitrianguar matrices over ${\mathbb{F}}_{p}$ ), $\textup{Inn}(H_{p})$ is $\Big\lparen k,\,\delta,\,\delta^{\frac{1}{k-3}}-o_{p}(1)\Big\rparen$ -testable for any $k\geq 4$ .

Additionally, we also get an upper bound of $\max_{\varphi}\operatorname{agr}{(f,\varphi)}\leq O(\delta^{\frac{1}{k}})$ , for any group $G$ and $k$ as above, except the dihedral group.

1.1.3 Lifting Homomorphism Tests

We give a general method to extend results for testability of known $\textup{Hom}(G,H)$ to those of $\textup{Hom}(\widetilde{G},H)$ in cases when $\textup{Hom}(\widetilde{G},H)$ factors through $\textup{Hom}(G,H)$ .

For instance, when $H$ is abelian, every homomorphism from $G$ to $H$ factors through an “abelianization” of $G$ , which is defined as $G/[G,G]$ where $[G,G]$ is the subgroup generated by $\langle xyx^{-1}y^{-1}\mid x,y\in G\rangle$ . This also works when we have a more general structure like a Lie algebra. We quickly define the notion of a character over a Lie algebra.

Lie algebra characters

A finite-dimensional Lie algebra, $\mathfrak{g}$ , is a finite-dimensional vector space over a field ${\mathbb{F}}$ with a Lie bracket $[\cdot,\cdot]:\mathfrak{g}\times\mathfrak{g}\rightarrow\mathfrak{g}$ which is a bilinear map such that

[x,x]=0\quad\text{and}\quad[x,[y,z]]+[y,[z,x]]+[z,[x,y]]=0,\;\;\forall\,x,y,z% \in\mathfrak{g}.

A linear character of a Lie algebra is a linear map $\varphi:\mathfrak{g}\rightarrow{\mathbb{F}}$ such that $f([x,y])=0$ for every $x,y\in\mathfrak{g}$ . Therefore, it is a linear map between vector spaces subject to an additional constraint. For example, let $\mathfrak{gl}_{n}(q)={\mathbb{F}}_{q}^{n\times n}$ , the vector space of $n\times n$ -matrices. The bracket is defined as $[x,y]:=xy-yx$ , where the multiplication is matrix multiplication. A character of $\mathfrak{gl}_{n}$ is a linear map with the property that $f(xy)=f(yx)$ for every pair of matrices $x, y$ .

Character testing has also been studied in the literature [1, 19, 21, 12, 18] for general groups (and more general representations). However, to the best of our knowledge, all known results work in the $L^{2}$ -metric, i.e., the soundness guarantee is in terms of $\lVert f(x)-\varphi\rVert_{2}^{2}$ . Our result gives the first character testing results for non-abelian groups in the Hamming metric.

Theorem 5 (Lifting results).

For the groups/Lie algebras mentioned in Table 2, one can obtain testing results by lifting from their base code. Moreover, the queries and soundness guarantees are identical to those of the base code.

Table 2: A summary of our lifting results.

Result	$G$	$H$	Base Code
Theorem 34	Any finite group	${\mathbb{F}}_{p}$	$\textup{Hom}({\mathbb{F}}_{p}^{n},{\mathbb{F}}_{p})$
Theorem 34	Any Lie Algebra over ${\mathbb{F}}_{p}$	${\mathbb{F}}_{p}$	$\textup{Hom}({\mathbb{F}}_{p}^{n},{\mathbb{F}}_{p})$
Theorem 33	$\mathrm{GL}_{n}(q),\;q\neq 2$	${\mathbb{F}}^{*}_{q}$	$\textup{Hom}({\mathbb{Z}}_{q-1},{\mathbb{Z}}_{q-1})$
Theorem 35	$\mathfrak{gl}_{n}(q)$	${\mathbb{F}}_{q}$	$\textup{Hom}({\mathbb{Z}}_{q},{\mathbb{Z}}_{q})$

Note: For the first result, $n$ is the $p$ -rank of $G$ , i.e., the $p$ -rank of its abelianization, or the rank of the Lie algebra.

$\blacktriangleright$ Remark 6.

In coding theory terms, the lifted homomorphism code (up to permutation) is the base code tensored with the repetition code of length $m=(\lvert\ker(\pi)\rvert)$ . Thus, one could alternatively design a test from this perspective, or appeal to results on local testability of tensor codes such as [9]. However, our approach yields the result easily by allowing us to mechanically reuse the analysis of the base code.

1.2 Technical Overview

For a function $f$ and a homomorphism $\varphi$ , let $\operatorname{agr}(f,\varphi)$ be the agreement between these functions, i.e., the fraction of inputs on which they agree. We wish to estimate $\max_{\varphi}\operatorname{agr}(f,\varphi)$ . To do this, we will define a distribution $\mathcal{F}$ on $\textup{Hom}(G,H)$ . Clearly,

\max_{\varphi\in\textup{Hom}(G,H)}\operatorname{agr}(f,\varphi)\nobreak\ \geq% \nobreak\ \mathchoice{\underset{\varphi\sim\mathcal{F}}{\mathbb{E}}\left[% \operatorname{agr}(f,\varphi)\right]}{{\mathbb{E}}_{\varphi\sim\mathcal{F}}[% \operatorname{agr}(f,\varphi)]}{{\mathbb{E}}_{\varphi\sim\mathcal{F}}[% \operatorname{agr}(f,\varphi)]}{{\mathbb{E}}_{\varphi\sim\mathcal{F}}[% \operatorname{agr}(f,\varphi)]}\;.

(1)

For this approximation to be useful, the distribution must have a large mass on homomorphisms that agree significantly with $f$ . A natural choice for such a distribution is ${\mathchoice{{\mathrm{Pr}}\left[\varphi\right]}{{\mathrm{Pr}}[\varphi]}{{% \mathrm{Pr}}[\varphi]}{{\mathrm{Pr}}[\varphi]}}\propto\operatorname{agr}(f,% \varphi)^{k}$ for some positive integer $k$ . Note that this is general and agnostic to the choice of groups (or even the fact that the code is a homomorphism code).

This expectation then becomes:

\mathchoice{\underset{\varphi\sim\mathcal{F}}{\mathbb{E}}\left[\operatorname{% agr}(f,\varphi)\right]}{{\mathbb{E}}_{\varphi\sim\mathcal{F}}[\operatorname{% agr}(f,\varphi)]}{{\mathbb{E}}_{\varphi\sim\mathcal{F}}[\operatorname{agr}(f,% \varphi)]}{{\mathbb{E}}_{\varphi\sim\mathcal{F}}[\operatorname{agr}(f,\varphi)% ]}\nobreak\ =\nobreak\ \frac{\sum_{\varphi}\operatorname{agr}(f,\varphi)^{k+1}% }{\sum_{\varphi}\operatorname{agr}(f,\varphi)^{k}}\;.

The next step is to estimate this expectation via a test that queries $f$ at only a few points. We do this by reinterpreting the expression for the $k^{\mathrm{th}}$ powers algebraically, using the knowledge that the code is a homomorphism code. The key point of the framework is that after this reinterpretation, the definition of a test pops quite intuitively, such that

{\sum_{\varphi\in\textup{Hom}(G,H)}\operatorname{agr}(f,\varphi)^{k}}\nobreak% \ \propto\nobreak\ {{\mathchoice{{\mathrm{Pr}}\left[f\;\text{ passes }\;% \mathsf{Test}_{k}\right]}{{\mathrm{Pr}}[f\;\text{ passes }\;\mathsf{Test}_{k}]% }{{\mathrm{Pr}}[f\;\text{ passes }\;\mathsf{Test}_{k}]}{{\mathrm{Pr}}[f\;\text% { passes }\;\mathsf{Test}_{k}]}}}.

(2)

Once we have this, the main testing result is a simple calculation. We now explain our algebraic reinterpretation of this expression and the test that emerges from it. The key to our method is the following evaluation map⁴⁴4We thank MO user t3suji whose comment on [7] was the inspiration for us to study this map. .

The evaluation map

One important way in which this framework utilizes the structure of $\textup{Hom}(G,H)$ , is that for any fixed tuple $\vec{x}=(x_{1},\dots,x_{k})\in G^{k}$ , there is a naturally associated evaluation map,

\Gamma_{\vec{x}}:\textup{Hom}(G,H)\rightarrow H^{k},\;\Gamma_{\vec{x}}(\varphi% )=(\varphi(x_{1}),\dots,\varphi(x_{k})).

While this map could be defined for any subset of functions (and not necessarily homomorphisms), for the set of homomorphisms, the map is $N$ -to-one on its image, where $N=\lvert\ker(\Gamma_{\vec{x}})\rvert$ . This crucial property immediately implies that,

\sum_{\varphi}\operatorname{agr}(f,\varphi)^{k}\nobreak\ =\nobreak\ % \mathchoice{\underset{\vec{x}\sim G^{k}}{\mathbb{E}}\left[\mathds{1}_{f(\vec{x% })\in\mathrm{Im}(\Gamma_{\vec{x}})}\cdot\lvert\ker(\Gamma_{\vec{x}})\rvert% \right]}{{\mathbb{E}}_{\vec{x}\sim G^{k}}[\mathds{1}_{f(\vec{x})\in\mathrm{Im}% (\Gamma_{\vec{x}})}\cdot\lvert\ker(\Gamma_{\vec{x}})\rvert]}{{\mathbb{E}}_{% \vec{x}\sim G^{k}}[\mathds{1}_{f(\vec{x})\in\mathrm{Im}(\Gamma_{\vec{x}})}% \cdot\lvert\ker(\Gamma_{\vec{x}})\rvert]}{{\mathbb{E}}_{\vec{x}\sim G^{k}}[% \mathds{1}_{f(\vec{x})\in\mathrm{Im}(\Gamma_{\vec{x}})}\cdot\lvert\ker(\Gamma_% {\vec{x}})\rvert]}.

The right-hand side can now be interpreted as a test wherein a tuple is sampled with a weight $\propto|\ker\Gamma_{\vec{x}}|$ , and the indicator $\mathds{1}_{f(\vec{x})\in\mathrm{Im}(\Gamma_{\vec{x}})}$ tests if there exists a homomorphism $\varphi$ with which $f$ agrees on the entire tuple $\vec{x}$ . This test trivially passes if $\mathrm{Im}(\Gamma_{\vec{x}})=H^{k}$ and thus we exclude such tuples. The final test is then,

${\sf Test}_{k}(G,H)$

$\blacksquare$

Sample $(x_{1},\dots,x_{k})\propto|\ker\Gamma_{\vec{x}}|$ subject to $\mathrm{Im}(\Gamma_{\vec{x}})\neq H^{k}$ .
$\blacksquare$

If $(f(x_{1}),\dots,f(x_{k}))\in\mathrm{Im}(\Gamma_{\vec{x}})$ : return $1$ ; otherwise: return $0$ .

Analyzing and adjusting the test

The above recipe works as it is for a given pair of groups if the following hold:

1.

Our approximation, i.e., Equation 1, is not too weak, and
2.

The test we have defined indeed approximates $\sum_{\varphi}\operatorname{agr}{(f,\varphi)}^{k}$ well.

Among the cases we analyze, this happens for cyclic (and cyclic-like) groups, and our results in Section 3 directly use this test. However, for $\textup{Hom}({\mathbb{F}}_{q}^{n},{\mathbb{F}}_{q})$ , the first condition does not hold. This is remedied by using a shifted variant of $\operatorname{agr}(f,\varphi)$ . Moreover, verifying the second point, i.e., checking if Equation 2 holds can be difficult in general, and another trick we employ is to define the test on a subset of all $k$ -tuples that makes the analysis more manageable. We wish to emphasize that ${\sf Test}_{k}(G,H)$ gives a starting point from which to derive a test for a general pair of groups.

1.3 Outline

We start in Section 1.4 by summarizing basic definitions and some of the notation used throughout the paper. The general testing framework developed in Section 2 captures the core methodology that is used throughout the paper to prove our main results.

As our first application, we use the proposed framework in Section 3 to establish the testing and list decoding results for cyclic groups. In particular, in Section 3.1, we prove the testing result, Theorem 15, for $G={\mathbb{Z}}_{p^{r}}$ and $H=\text{abelian group of bounded }p$ -rank; here, we also prove the list decoding theorem, Theorem 16. In Section 3.2, we generalize to the case when $G$ and $H$ are arbitrary cyclic groups.

We focus on vector spaces in Section 4. The main result of this section is Theorem 27 that allows us to test functions from ${\mathbb{F}}_{q}^{n}\rightarrow{\mathbb{F}}_{q}$ . In the same section, we also derive a testing result (Theorem 30) for $\textup{Hom}({\mathbb{F}}_{q},{\mathbb{F}}^{n}_{q})$ .

In Section 5 and Section 6, we consider the non-abelian setting. Section 5 focuses on testing for closeness to an automorphism or an inner automorphism. We look at dihedral groups (Theorem 31), symmetric group, quasirandom groups, and more generally, finite simple groups (Theorem 32). Finally, in Section 6, we prove a general lifting theorem. This allows us to prove our character testing results (Theorems 33 and 35), and other lifted results Theorem 34.

1.4 Prelims

Fact 7 ( $p$ -components of Abelian groups).

Every finite abelian group decomposes into $G=\oplus_{p}G_{p}$ where $G_{p}=\oplus_{i}{\mathbb{Z}}_{p^{b_{i}}}$ is the $p$ -component of $G$ . The $p$ -rank of $G$ is the number of summands in $G_{p}$ . Moreover, $\textup{Hom}(G,H)\cong\oplus_{p}\textup{Hom}(G_{p},H_{p})$ .

Fact 8 (Cyclic Homomorphisms).

Let $G={\mathbb{Z}}_{p^{r}}$ and $H$ be any abelian group with a $p$ -component $\oplus_{i}{\mathbb{Z}}_{p^{b_{i}}}$ . Then, $\textup{Hom}(G,H)=\oplus_{i}{\mathbb{Z}}_{p^{\min(r,b_{i})}}$ , and thus, $\lvert\textup{Hom}(G,H)\rvert\leq|H|$ .

Proof.

Any homomorphism $\varphi:{\mathbb{Z}}_{p^{r}}\rightarrow{\mathbb{Z}}_{p^{b}}$ , is determined by $\varphi(1)$ which must have order $p^{a_{\varphi}}\leq p^{\min(r,b)}$ . For a given order $p^{j}$ , the number of elements with order at most $j$ is $p^{j}$ and thus $\textup{Hom}(G,H)={\mathbb{Z}}_{p}^{\min(r,b)}$ . $\hfill\blacktriangleleft$

Notation.

Let $f:G\rightarrow H$ be a function. For any ${\vec{x}}=(x_{1},\dots,x_{k})\in G^{k}$ , we use the shorthand: $f(\vec{x}):=(f(x_{1}),\dots,f(x_{k}))$ .

2 A General Test

For any, $\vec{x}\in G^{k}$ , we define the following evaluation map:

\Gamma_{\vec{x}}:\textup{Hom}(G,H)\rightarrow H^{k}\nobreak\ :\nobreak\ \Gamma% _{\vec{x}}(\varphi)=\lparen\varphi(x_{1}),\dots,\varphi(x_{k})\rparen\;.

Because $H$ is an abelian group, the set $\textup{Hom}(G,H)$ is an abelian group under pointwise multiplication. Moreover, the maps $\{\Gamma_{\vec{x}}\}_{\vec{x}}$ are homomorphisms. We make the following important definitions that we will use throughout:

{\sf H}_{\vec{x}}:=\operatorname{Im}\lparen\Gamma_{\vec{x}}\rparen\leqslant H^% {k},\quad\mathcal{G}_{k}:=\big\{\vec{x}\in G^{k}\mid{\sf H}_{\vec{x}}\neq H^{k% }\big\},\quad\eta_{k}=\frac{|\mathcal{G}_{k}|}{|G^{k}|}\;.

Lemma 9 (Rewriting the agreement).

Let $G, H$ be finite abelian groups, and let $f:G\rightarrow H$ be any function.

\sum_{\varphi\in\textup{Hom}(G,H)}\operatorname{agr}{(f,\varphi)}^{k}\nobreak% \ =\nobreak\ \eta_{k}\cdot\mathchoice{\underset{\vec{x}\sim\mathcal{G}_{k}}{% \mathbb{E}}\left[\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}\lvert\ker(\Gamma_% {\vec{x}})\rvert\right]}{{\mathbb{E}}_{\vec{x}\sim\mathcal{G}_{k}}[\mathds{1}_% {f(\vec{x})\in{\sf H}_{\vec{x}}}\lvert\ker(\Gamma_{\vec{x}})\rvert]}{{\mathbb{% E}}_{\vec{x}\sim\mathcal{G}_{k}}[\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}% \lvert\ker(\Gamma_{\vec{x}})\rvert]}{{\mathbb{E}}_{\vec{x}\sim\mathcal{G}_{k}}% [\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}\lvert\ker(\Gamma_{\vec{x}})\rvert% ]}+(1-\eta_{k})\cdot\frac{\lvert\textup{Hom}(G,H)\rvert}{\lvert H^{k}\rvert}\;.

Proof.

See the full version for the proof. $\hfill\blacktriangleleft$

General Test

Motivated by the non-constant term in the expression, we define the distribution on $\mathcal{G}_{k}$ which samples $x\propto|\ker(\Gamma_{\vec{x}})|$ , i.e.,

\mathcal{D}_{\ker}(\vec{x})\nobreak\ :=\nobreak\ \frac{|\ker(\Gamma_{\vec{x}})% |}{\sum_{\vec{x}\in\mathcal{G}_{k}}|\ker(\Gamma_{\vec{x}})|}\;\;.

${\sf Test}\_{\ker}_{k}(G,H)$

$\blacksquare$

Sample $\vec{x}\sim\mathcal{D}_{\ker}$ , i.e., $\vec{x}\in\mathcal{G}_{k}\propto\lvert\ker(\Gamma_{\vec{x}})\rvert$ .
$\blacksquare$

If $f(\vec{x})\in{\sf H}_{\vec{x}}$ : return $1$ ; otherwise: return $0$ .

Corollary 10 (Test passing Probability).

Let $f:G\rightarrow H$ and $\delta_{k}$ be the probability that $f$ passes the ${\sf Test}\_{\ker}_{k}(G,H)$ . Then,

\delta_{k}\nobreak\ =\nobreak\ \frac{\mathchoice{\underset{\vec{x}\sim\mathcal% {G}_{k}}{\mathbb{E}}\left[\mathds{1}_{f(\vec{x})\in H_{x}}\lvert\ker(\Gamma_{% \vec{x}})\rvert\right]}{{\mathbb{E}}_{\vec{x}\sim\mathcal{G}_{k}}[\mathds{1}_{% f(\vec{x})\in H_{x}}\lvert\ker(\Gamma_{\vec{x}})\rvert]}{{\mathbb{E}}_{\vec{x}% \sim\mathcal{G}_{k}}[\mathds{1}_{f(\vec{x})\in H_{x}}\lvert\ker(\Gamma_{\vec{x% }})\rvert]}{{\mathbb{E}}_{\vec{x}\sim\mathcal{G}_{k}}[\mathds{1}_{f(\vec{x})% \in H_{x}}\lvert\ker(\Gamma_{\vec{x}})\rvert]}}{\mathchoice{\underset{\vec{x}% \sim\mathcal{G}_{k}}{\mathbb{E}}\left[\left\lvert\ker(\Gamma_{\vec{x}})\right% \rvert\right]}{{\mathbb{E}}_{\vec{x}\sim\mathcal{G}_{k}}[\left\lvert\ker(% \Gamma_{\vec{x}})\right\rvert]}{{\mathbb{E}}_{\vec{x}\sim\mathcal{G}_{k}}[% \left\lvert\ker(\Gamma_{\vec{x}})\right\rvert]}{{\mathbb{E}}_{\vec{x}\sim% \mathcal{G}_{k}}[\left\lvert\ker(\Gamma_{\vec{x}})\right\rvert]}}\;\;.

And therefore,

\sum_{\varphi}\operatorname{agr}{(f,\varphi)}^{k}\nobreak\ =\nobreak\ \delta_{% k}\cdot\eta_{k}\cdot\mathchoice{\underset{\vec{x}\sim\mathcal{G}_{k}}{\mathbb{% E}}\left[\left\lvert\ker(\Gamma_{\vec{x}})\right\rvert\right]}{{\mathbb{E}}_{% \vec{x}\sim\mathcal{G}_{k}}[\left\lvert\ker(\Gamma_{\vec{x}})\right\rvert]}{{% \mathbb{E}}_{\vec{x}\sim\mathcal{G}_{k}}[\left\lvert\ker(\Gamma_{\vec{x}})% \right\rvert]}{{\mathbb{E}}_{\vec{x}\sim\mathcal{G}_{k}}[\left\lvert\ker(% \Gamma_{\vec{x}})\right\rvert]}\nobreak\ +\nobreak\ (1-\eta_{k})\cdot\frac{% \textup{Hom}(G,H)}{|H|^{k}}.

The following claim merely gives an alternate way to compute the term on the RHS of the above equation, i.e., the expected kernel size.

Claim 11.

For any finite groups $G, H$ , and $k\geq 1$ , we have

\gamma_{k}\nobreak\ :=\nobreak\ \sum_{\vec{x}\in G^{k}}{\left\lvert\ker(\Gamma% _{\vec{x}})\right\rvert}\nobreak\ \nobreak\ =\sum_{\varphi\in\textup{Hom}(G,H)% }{\lvert\ker(\varphi)\rvert^{k}}.

Proof.

See the full version for the proof. $\hfill\vartriangleleft$

Summarizing the expressions

We now summarize the expressions we need for ready reference in our proofs.

$\displaystyle\max_{\varphi}\operatorname{agr}{(f,\varphi)}\nobreak\$	$\displaystyle\geq\nobreak\ \frac{\sum_{\varphi}\operatorname{agr}{(f,\varphi)}% ^{k+1}}{\sum_{\varphi}\operatorname{agr}{(f,\varphi)}^{k}}$	(3)
$\displaystyle\sum_{\varphi}\operatorname{agr}{(f,\varphi)}^{k}\nobreak\$	$\displaystyle=\nobreak\ \mathchoice{\underset{\vec{x}\sim G^{k}}{\mathbb{E}}% \left[\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}\lvert\ker(\Gamma_{\vec{x}})% \rvert\right]}{{\mathbb{E}}_{\vec{x}\sim G^{k}}[\mathds{1}_{f(\vec{x})\in{\sf H% }_{\vec{x}}}\lvert\ker(\Gamma_{\vec{x}})\rvert]}{{\mathbb{E}}_{\vec{x}\sim G^{% k}}[\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}\lvert\ker(\Gamma_{\vec{x}})% \rvert]}{{\mathbb{E}}_{\vec{x}\sim G^{k}}[\mathds{1}_{f(\vec{x})\in{\sf H}_{% \vec{x}}}\lvert\ker(\Gamma_{\vec{x}})\rvert]}$	(4)
	$\displaystyle=\nobreak\ \eta_{k}\cdot\mathchoice{\underset{\vec{x}\sim\mathcal% {G}_{k}}{\mathbb{E}}\left[\mathds{1}_{f(\vec{x})\in{{\sf H}}_{x}}\lvert\ker(% \Gamma_{\vec{x}})\rvert\right]}{{\mathbb{E}}_{\vec{x}\sim\mathcal{G}_{k}}[% \mathds{1}_{f(\vec{x})\in{{\sf H}}_{x}}\lvert\ker(\Gamma_{\vec{x}})\rvert]}{{% \mathbb{E}}_{\vec{x}\sim\mathcal{G}_{k}}[\mathds{1}_{f(\vec{x})\in{{\sf H}}_{x% }}\lvert\ker(\Gamma_{\vec{x}})\rvert]}{{\mathbb{E}}_{\vec{x}\sim\mathcal{G}_{k% }}[\mathds{1}_{f(\vec{x})\in{{\sf H}}_{x}}\lvert\ker(\Gamma_{\vec{x}})\rvert]}% +(1-\eta_{k})\cdot\frac{\lvert\textup{Hom}(G,H)\rvert}{\lvert H^{k}\rvert}$	(5)
	$\displaystyle=\nobreak\ \delta_{k}\cdot\frac{\gamma_{k}}{\|G\|^{k}}+(1-\eta_{k})% \cdot\frac{\lvert\textup{Hom}(G,H)\rvert}{\lvert H^{k}\rvert}.$	(6)

3 Cyclic Groups

3.1 Cyclic groups of prime power order to abelian groups of small rank

We will first start with both the domain being a cyclic group of prime power order. For such groups, the expression from Corollary 10 can be further simplified, as $\eta_{k}=1$ .

Observation 12.

Let $G={\mathbb{Z}}_{p^{r}}$ and $H$ be any abelian group. Then, for any $k\geq 2$ , $\eta_{k}(G,H)=1$ and thus, for any $f:G\rightarrow H$ ,

\sum_{\varphi\in\textup{Hom}(G,H)}\operatorname{agr}{(f,\varphi)}^{k}\nobreak% \ =\nobreak\ \delta_{k}(f)\cdot\frac{\gamma_{k}}{|G|^{k}}\;\;.

Proof.

See the full version for the proof. $\hfill\blacktriangleleft$

Bounding $\gamma_{k}$

From the expression it is clear that the only quantity we need to analyze is $\gamma_{k}$ which we will do via Claim 11.

Lemma 13 (Cyclic to Abelian).

Let $G={\mathbb{Z}}_{p^{r}}$ and $H$ any abelian group. Then,

\gamma_{k}(G,H)\nobreak\ =\nobreak\ \big\lvert\textup{Hom}({\mathbb{Z}}_{p^{r}% },H)\big\rvert+\lparen 1-p^{-k}\rparen\sum_{a=1}^{r}p^{ak}\cdot\big\lvert% \textup{Hom}({\mathbb{Z}}_{p^{r-a}},H)\big\rvert.

Proof.

See the full version for the proof. $\hfill\blacktriangleleft$

Note that due to Fact 7, any homomorphism maps ${\mathbb{Z}}_{p^{r}}$ only to a $p$ -group. Since, $\gamma_{k}$ only concerns homomorphisms, it is only dependent on the $p$ -component $H_{p}:=\oplus_{i=1}^{t}{\mathbb{Z}}_{p^{b_{i}}}$ . Here, $t$ is the $p$ -rank of $H$ . We now explicitly bound $\gamma_{k}$ for $k$ larger that the $p$ -rank of $H$ .

Corollary 14.

Let $G={\mathbb{Z}}_{p^{r}}$ , and let $H$ be an abelian group of $p$ -rank $t$ , and let $k>t$ . Then,

(1-p^{-k})\cdot p^{kr}\nobreak\ \leq\nobreak\ \gamma_{k}(G,H)\nobreak\ \leq% \nobreak\ \Big\lparen\frac{p^{k-t}}{p^{k-t}-1}\Big\rparen\cdot p^{kr}.

Proof.

See the full version for the proof. $\hfill\blacktriangleleft$

We can now use the above calculation for $\gamma_{k}$ to deduce a testing result, and a (combinatorial) list decoding bound.

Theorem 15 (Testing prime power cyclic groups to Abelian groups of bounded rank).

Let $G={\mathbb{Z}}_{p^{r}}$ be a cyclic group and $H$ be an abelian group of $p$ -rank $t\geq 1$ . Let $k\geq t+2$ be an integer, and let $f:G\rightarrow H$ be any function. Then if $f$ passes ${\sf Test}\_\ker_{k}(G,H)$ with probability $\delta_{k}$ , then,

\Big\lparen\frac{(p-1)^{2}}{p^{2}}\cdot\delta_{k}\Big\rparen^{\frac{1}{k-t-1}}% \nobreak\ \leq\nobreak\ \operatorname{agr}(f,\varphi)\nobreak\ \leq\nobreak\ % \Big\lparen\frac{p^{2}}{p^{2}-1}\delta_{k}\Big\rparen^{\frac{1}{k}}\;.

Proof.

The upper bound directly follows from Observation 12 and Corollary 14. For the lower bound we use Equation 3 and Observation 12 to get,

\displaystyle\max_{\varphi}\,\operatorname{agr}(f,\varphi)\nobreak\

\displaystyle\geq\nobreak\ \frac{\sum_{\varphi}{\operatorname{agr}(f,\varphi)^% {i}}}{\sum_{\varphi}{\operatorname{agr}(f,\varphi)^{i-1}}}\nobreak\ \geq% \nobreak\ \frac{\delta_{i}\gamma_{i}}{|G|\delta_{i-1}\gamma_{i-1}}.

Multiplying this for $i\in[t+2,k]$ , we get

$\displaystyle\lparen\max_{\varphi}\operatorname{agr}(f,\varphi)\rparen^{k-t-1}\nobreak\$	$\displaystyle\geq\nobreak\ \Big\lparen\frac{1}{\|G\|}\Big\rparen^{k-t}\cdot\frac% {\delta_{k}\gamma_{k}}{\delta_{t+1}\gamma_{t+1}}$
	$\displaystyle\geq\nobreak\ \Big\lparen\frac{1}{\|G\|}\Big\rparen^{k-t-1}\cdot% \frac{\delta_{k}\gamma_{k}}{\gamma_{t+1}}$	$\displaystyle[\delta_{t+1}\leq 1]$
	$\displaystyle\geq\nobreak\ \delta_{k}\cdot\frac{(1-p^{-k})(p-1)}{p}$	$\displaystyle[\text{Using\nobreak\ \lx@cref{creftype~refnum}{cor:boundedrank}}]$
	$\displaystyle\geq\nobreak\ \delta_{k}\cdot\frac{(p-1)^{2}}{p^{2}}$

$\hfill\blacktriangleleft$

Using the above bound we also immediately get a list decoding bound.

Theorem 16 (List Size Bound).

Let $G={\mathbb{Z}}_{p^{r}}$ be a cyclic group and $H$ be an abelian group of $p$ -rank $t\geq 1$ . Let $f:G\rightarrow H$ be any function. Then the following holds:

\lvert\{\varphi\in\textup{Hom}(G,H)\nobreak\ :\nobreak\ \operatorname{agr}(f,% \varphi)\nobreak\ \geq\nobreak\ \varepsilon\}\rvert\nobreak\ \leq\nobreak\ % \Big\lparen\frac{p}{p-1}\Big\rparen\cdot\frac{1}{\varepsilon^{t+1}}.

In particular, we get a list size bound of $\frac{2}{\varepsilon^{2}}$ for homomorphisms between cyclic groups.

Proof.

Let $N=\lvert\{\varphi\in\hom(G,H)\nobreak\ :\nobreak\ \operatorname{agr}(f,\varphi% )\nobreak\ \geq\nobreak\ \varepsilon\}\rvert$ . Then,

	$\displaystyle N\varepsilon^{t+1}\nobreak\ \leq\nobreak\ \sum_{\varphi}\alpha_{% \varphi}^{t+1}\nobreak\$	$\displaystyle=\nobreak\ \frac{\delta_{t+1}\gamma_{t+1}}{\|G\|^{t+1}}$
		$\displaystyle\leq\nobreak\ \frac{p}{p-1}$	$\displaystyle[\text{Using\nobreak\ \lx@cref{creftype~refnum}{cor:boundedrank}}% ].\$

$\hfill\blacktriangleleft$

3.2 Arbitrary Cyclic groups

To handle general cyclic groups, we will use the decomposition of abelian groups into their $p$ -components.

Lemma 17 (Reduction to p-groups).

Let $\varphi:G\rightarrow H$ , and let $X=\oplus_{p}X_{p}$ for $X\in\{G,H\}$ be the decomposition of the groups into their p-components. Then, $\varphi=\oplus\varphi_{p}$ where $\varphi_{p}:G_{p}\rightarrow H_{p}$ . Therefore,

	$\displaystyle\gamma_{k}(G,H)\nobreak\$	$\displaystyle=\nobreak\ \prod_{p}\gamma_{k}(G_{p},H_{p}),$
	$\displaystyle 1-\eta_{k}(G,H)\nobreak\$	$\displaystyle=\nobreak\ \prod_{p}\lparen 1-\eta_{k}(G_{p},H_{p})\rparen.$

Proof.

See the full version for the proof. $\hfill\blacktriangleleft$

Definition 18 (Riemann Zeta Function).

Define the Riemann zeta function using Euler’s product formula as $\zeta(s)=\prod_{p}(1-\frac{1}{p^{s}})^{-1}$ where the product runs over all primes.

Proposition 19.

Let $G, H$ be any cyclic groups and let $k\geq 3$ . Denote by $\zeta()$ , the Riemann zeta function. Then,

|G|^{k}\nobreak\ \leq\nobreak\ \gamma_{k}(G,H)\nobreak\ \leq\nobreak\ |G|^{k}% \cdot\zeta(k-1)^{2}.

Proof.

See the full version for the proof. $\hfill\blacktriangleleft$

Theorem 20 (Testing $\textup{Hom}({\mathbb{Z}}_{n},{\mathbb{Z}}_{m})$ ).

Let $G, H$ be any cyclic groups and $f:G\rightarrow H$ be any function. Let $k\geq 4$ be any integer. Then if $f$ passes ${\sf Test}\_\ker_{k}(G,H)$ with probability $\delta_{k}$ , then there exists a homomorphism $\varphi\in\textup{Hom}(G,H)$ such that $\operatorname{agr}(f,\varphi)\nobreak\ \geq\nobreak\ \big\lparen\zeta(2)^{2}% \cdot\delta_{k}\big\rparen^{\frac{1}{k-3}}$ .

Proof.

By Lemma 17, $\eta(G,H)=1$ for any pair of cyclic groups, and thus, the expression from Observation 12 holds. Using it,

\displaystyle\max_{\varphi}\,\operatorname{agr}(f,\varphi)\nobreak\

\displaystyle\geq\nobreak\ \frac{\sum_{\varphi}{\operatorname{agr}(f,\varphi)^% {i}}}{\sum_{\varphi}{\operatorname{agr}(f,\varphi)^{i-1}}}\nobreak\ \geq% \nobreak\ \frac{\delta_{i}\gamma_{i}}{|G|\delta_{i-1}\gamma_{i-1}}.

Multiplying this for $i\in[4,k]$ , we get

$\displaystyle\lparen\max_{\varphi}\operatorname{agr}(f,\varphi)\rparen^{k-t-1}\nobreak\$	$\displaystyle\geq\nobreak\ \Big\lparen\frac{1}{\|G\|}\Big\rparen^{k-t}\cdot\frac% {\delta_{k}\gamma_{k}}{\delta_{t+1}\gamma_{t+1}}$
	$\displaystyle\geq\nobreak\ \Big\lparen\frac{1}{\|G\|}\Big\rparen^{k-t-1}\cdot% \frac{\delta_{k}\cdot\gamma_{k}}{\gamma_{t+1}}$	$\displaystyle[\delta_{t+1}\leq 1]$
	$\displaystyle\geq\nobreak\ \delta_{k}\cdot\frac{(1-p^{-k})(p-1)}{p}$	$\displaystyle[\text{Using\nobreak\ \lx@cref{creftype~refnum}{cor:boundedrank}}]$
	$\displaystyle\geq\nobreak\ \delta_{k}\cdot\frac{(p-1)^{2}}{p^{2}}\;.$

$\hfill\blacktriangleleft$

4 Vector space over finite fields

Let, ${\mathbb{F}}_{q}$ be a finite field of order $q$ . In this section, we will focus on functions between a ${\mathbb{F}}_{q}$ -vector space and the finite field, ${\mathbb{F}}_{q}$ .

4.1 Vector space to Finite Field

Let, $G={\mathbb{F}}^{n}_{q}$ and $H={\mathbb{F}}_{q}$ . Let $f:G\rightarrow H$ be an arbitrary function.

A shifted variant of agreement

We first recall the expression for $\sum_{\varphi}\operatorname{agr}{(f,\varphi)}^{k}$ from Section 2.

\sum_{\varphi\in\textup{Hom}(G,H)}\operatorname{agr}{(f,\varphi)}^{k}\nobreak% \ =\nobreak\ \delta_{k}\cdot\eta_{k}\cdot\mathchoice{\underset{\vec{x}\sim% \mathcal{G}_{k}}{\mathbb{E}}\left[\left\lvert\ker(\Gamma_{\vec{x}})\right% \rvert\right]}{{\mathbb{E}}_{\vec{x}\sim\mathcal{G}_{k}}[\left\lvert\ker(% \Gamma_{\vec{x}})\right\rvert]}{{\mathbb{E}}_{\vec{x}\sim\mathcal{G}_{k}}[% \left\lvert\ker(\Gamma_{\vec{x}})\right\rvert]}{{\mathbb{E}}_{\vec{x}\sim% \mathcal{G}_{k}}[\left\lvert\ker(\Gamma_{\vec{x}})\right\rvert]}\nobreak\ +% \nobreak\ (1-\eta_{k})\cdot\frac{\textup{Hom}(G,H)}{|H|^{k}},

where $\delta_{k}$ is the test passing probability of the general test (that samples $\vec{x}\propto|\ker\Gamma_{\vec{x}}|$ and checks $\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}$ ) given in Section 2. A key difference in the vector space case compared to the cyclic case is that $\eta_{k}\approx 0$ . Therefore most of the contribution in $\sum_{\varphi\in\textup{Hom}(G,H)}\operatorname{agr}{(f,\varphi)}^{k}$ comes from the non-test part: $\textup{Hom}(G,H)\cdot H^{-k}$ . This happens because any function has roughly $\frac{1}{q}$ -agreement with many homomorphisms (at least $\frac{1}{2q}$ -fraction of all homomorphisms). In particular, it is easy to see that if $f$ is a random function then it has $\frac{1}{q}$ -agreement with almost all the homomorphisms. This suggests adjusting the definition of agreement, $\operatorname{agr}{(f,\varphi)}$ , so that it measures the non-trivial advantage over the trivial agreement of $\frac{1}{q}$ . To achieve this we define the following shifted variant of $\operatorname{agr}{(f,\varphi)}$ .

\textbf{Shifted agreement: }\nobreak\ \nobreak\ \widetilde{\operatorname{agr}}% (f,\varphi)=\frac{q\operatorname{agr}{(f,\varphi)}-1}{q-1}

Accordingly, we will use the expression $\sum_{\varphi}\widetilde{\operatorname{agr}}(f,\varphi)^{k}$ instead of $\sum_{\varphi}\operatorname{agr}{(f,\varphi)}^{k}$ so that distribution concentrates on homomorphisms with non-trivial agreements. Fortunately, the former expression can be directly computed from the latter via binomial expansion.

Refining the test

We need to address one more issue in this vector space setting. We cannot directly use the original generalized test that - samples $\vec{x}$ with probability $\propto|\ker\Gamma_{\vec{x}}|$ and checks $f(\vec{x})\in{\sf H}_{\vec{x}}$ . This is because even though this test uses length $k$ -tuple, it can happen that sampled the tuple satisfy only linear relation involving $j$ (for some $j<k$ ) co-ordinates of the input and all the rest of the co-ordinates are independent. If this happens, then the test essentially collapses to a $j$ -th level test involving $j$ -length tuple - as it essentially checks if $f$ satisfy that linear relation or not. In other words, the generalized test is a linear combination of such different tests associated with different levels. For a precise analysis, it is crucial to refine the initial test definition and isolate these different tests. To do this, we need to formalize this notion of tuples satisfiying a linear relation involving $j$ -coordinates.

Definition 21 (A level- $j$ distribution).

We define ${\mathcal{R}}_{j}$ to be the set of tuples $\vec{x}\in G^{k}$ such that (1) there exist $\emptyset\neq S\subseteq[k]$ with $|S|=j$ such that $\sum_{\ell\in S}a_{\ell}x_{\ell}=0$ for non-zero coefficients $\{a_{\ell}\}_{\ell\in S}$ and (2) vectors in $\vec{x}$ do not satisfy any other linear relation.

Observe that the sets ${\mathcal{R}}_{j}$ for distinct $j$ are disjoint. Now we collect all the claims involving ${\mathcal{R}}_{j}$ and linear independence of tuples, that will be needed for our analysis. For any two quantities, ${\sf t}_{1}$ and ${\sf t}_{2}$ : we write ${\sf t}_{1}\approx_{\varepsilon}{\sf t}_{2}$ if $\lvert{\sf t}_{1}-{\sf t}_{2}\rvert=O(\varepsilon).$ Our first claim is the following:

Claim 22.

Let, $k\geq 1$ be any integer such that $k=O_{n}(1)$ . Then it holds that,

1.

$\mathchoice{\underset{\vec{x}\sim G^{k}}{\mathrm{Pr}}\left[\operatorname{rank}% (\vec{x})=k\right]}{{\mathrm{Pr}}_{\vec{x}\sim G^{k}}[\operatorname{rank}(\vec% {x})=k]}{{\mathrm{Pr}}_{\vec{x}\sim G^{k}}[\operatorname{rank}(\vec{x})=k]}{{% \mathrm{Pr}}_{\vec{x}\sim G^{k}}[\operatorname{rank}(\vec{x})=k]}\approx_{q^{-% 2n}}\Big\lparen 1-\frac{q^{k}-1}{q^{n}(q-1)}\Big\rparen$ .
2.

$\mathchoice{\underset{\vec{x}\in G^{k}}{\mathrm{Pr}}\left[\vec{x}\in{\mathcal{% R}}_{j}\right]}{{\mathrm{Pr}}_{\vec{x}\in G^{k}}[\vec{x}\in{\mathcal{R}}_{j}]}% {{\mathrm{Pr}}_{\vec{x}\in G^{k}}[\vec{x}\in{\mathcal{R}}_{j}]}{{\mathrm{Pr}}_% {\vec{x}\in G^{k}}[\vec{x}\in{\mathcal{R}}_{j}]}\approx_{q^{-2n}}\binom{k}{j}% \frac{(q-1)^{j-1}}{q^{n}}$ .

Proof.

See the full version for the proof. $\hfill\vartriangleleft$

Claim 23.

Let, $1\leq j\leq k$ be two integers. Then,

\mathchoice{\underset{\vec{x}\sim G^{k}}{\mathbb{E}}\left[\mathds{1}_{f(\vec{x% })\in{\sf H}_{\vec{x}}}|\vec{x}\in{\mathcal{R}}_{j}\right]}{{\mathbb{E}}_{\vec% {x}\sim G^{k}}[\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}|\vec{x}\in{\mathcal% {R}}_{j}]}{{\mathbb{E}}_{\vec{x}\sim G^{k}}[\mathds{1}_{f(\vec{x})\in{\sf H}_{% \vec{x}}}|\vec{x}\in{\mathcal{R}}_{j}]}{{\mathbb{E}}_{\vec{x}\sim G^{k}}[% \mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}|\vec{x}\in{\mathcal{R}}_{j}]}% \nobreak\ =\nobreak\ \mathchoice{\underset{\vec{x}\sim G^{j}}{\mathbb{E}}\left% [\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}|\vec{x}\in{\mathcal{R}}_{j}\right% ]}{{\mathbb{E}}_{\vec{x}\sim G^{j}}[\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}% }|\vec{x}\in{\mathcal{R}}_{j}]}{{\mathbb{E}}_{\vec{x}\sim G^{j}}[\mathds{1}_{f% (\vec{x})\in{\sf H}_{\vec{x}}}|\vec{x}\in{\mathcal{R}}_{j}]}{{\mathbb{E}}_{% \vec{x}\sim G^{j}}[\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}|\vec{x}\in{% \mathcal{R}}_{j}]}\;.

Proof.

See the full version for the proof. $\hfill\vartriangleleft$

Analyzing the key expression

Let us now examine the expression for $\sum_{\varphi}\operatorname{agr}{(f,\varphi)}^{k}$ , from which the appropriate definition of the test becomes apparent.

Claim 24.

Let, $k\geq 1$ be any integer, and $f:{\mathbb{F}}_{q}^{n}\rightarrow{\mathbb{F}}_{q}$ be any function. Then,

\sum_{\varphi}\operatorname{agr}{(f,\varphi)}^{k}\nobreak\ \approx_{q^{-n}}% \nobreak\ \mathchoice{\underset{\vec{x}\sim G^{k}}{\mathrm{Pr}}\left[% \operatorname{rank}(\vec{x})=k\right]}{{\mathrm{Pr}}_{\vec{x}\sim G^{k}}[% \operatorname{rank}(\vec{x})=k]}{{\mathrm{Pr}}_{\vec{x}\sim G^{k}}[% \operatorname{rank}(\vec{x})=k]}{{\mathrm{Pr}}_{\vec{x}\sim G^{k}}[% \operatorname{rank}(\vec{x})=k]}\cdot q^{n-k}+q^{-(k-1)}\cdot\sum^{k}_{j=1}% \binom{k}{j}(q-1)^{j-1}\delta_{j}(f)\;,

where $\delta_{j}(f)\nobreak\ :=\nobreak\ \mathchoice{\underset{\vec{x}\sim G^{j}}{% \mathbb{E}}\left[\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}|\vec{x}\in{% \mathcal{R}}_{j}\right]}{{\mathbb{E}}_{\vec{x}\sim G^{j}}[\mathds{1}_{f(\vec{x% })\in{\sf H}_{\vec{x}}}|\vec{x}\in{\mathcal{R}}_{j}]}{{\mathbb{E}}_{\vec{x}% \sim G^{j}}[\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}|\vec{x}\in{\mathcal{R}% }_{j}]}{{\mathbb{E}}_{\vec{x}\sim G^{j}}[\mathds{1}_{f(\vec{x})\in{\sf H}_{% \vec{x}}}|\vec{x}\in{\mathcal{R}}_{j}]}.$

Proof.

See the full version for the proof. $\hfill\vartriangleleft$

Defining the refined test

Inspired from Claim 24 we define a $k^{\mathrm{th}}$ test such that the test passing probability of a function $f$ is $\delta_{k}(f)$ as above, i.e.,

\delta_{k}(f):=\mathchoice{\underset{\vec{x}\in G^{k}}{\mathbb{E}}\left[% \mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}|\vec{x}\in{\mathcal{R}}_{k}\right]% }{{\mathbb{E}}_{\vec{x}\in G^{k}}[\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}|% \vec{x}\in{\mathcal{R}}_{k}]}{{\mathbb{E}}_{\vec{x}\in G^{k}}[\mathds{1}_{f(% \vec{x})\in{\sf H}_{\vec{x}}}|\vec{x}\in{\mathcal{R}}_{k}]}{{\mathbb{E}}_{\vec% {x}\in G^{k}}[\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}|\vec{x}\in{\mathcal{% R}}_{k}]}.

${{\sf Test}\_\mathsf{VSpace}}_{k}(f)$

$\blacksquare$

Sample $(x_{1},\dots,x_{k})\sim{\mathcal{R}}_{k}$ .
$\blacksquare$

If $(f(x_{1}),\dots,f(x_{k}))\in{\sf H}_{\vec{x}}$ : return $1$ ; otherwise: return $0$

Or equivalently,

$\blacksquare$

Sample $k-1$ independent vectors: $x_{1},\dots,x_{k-1}$ .
$\blacksquare$

Sample $a_{1},\dots,a_{k-1}\sim{\mathbb{F}}_{q}\setminus\{0\}$ and set $x_{k}=\sum^{k-1}_{i}a_{i}x_{i}$
$\blacksquare$

If $f(x_{k})=a_{1}f(x_{1})+a_{2}f(x_{2})+\dots+a_{k-1}f(x_{k-1})$ : return $1$ ; otherwise: return $0$

Analysis of the Test

We state a simple combinatorial fact that we will need.

Fact 25 (Binomial Identity).

Let $0\leq j<k$ be any integers. Then,

\sum^{k}_{i=j}(-1)^{k-i}\binom{k}{i}\binom{i}{j}\nobreak\ =\nobreak\ 0\;.

Proof.

A direct corollary of the fact that $\binom{k}{i}\binom{i}{j}=\binom{k}{j}\binom{k-j}{i-j}$ . $\hfill\blacktriangleleft$

Corollary 26.

Let $k\geq 1$ be any integer.

\sum_{\varphi}\widetilde{\operatorname{agr}}(f,\varphi)^{k}\nobreak\ \approx_{% q^{-n}}\nobreak\ \frac{1}{q-1}(q\delta_{k}-1).

Proof.

See the full version for the proof. $\hfill\blacktriangleleft$

Theorem 27.

Let $G={\mathbb{F}}^{n}_{q}$ be a vector space and $H={\mathbb{F}}_{q}$ for some finite field of order $q$ . Let $k\geq 3$ be any odd integer. Then if $f$ passes ${\sf Test}\_\mathsf{VSpace}_{k}(f)$ with probability $\delta_{k}>\frac{1}{q}$ , then,

\frac{1}{q}+\big\lparen\frac{q-1}{q}\big\rparen\Big\lparen\frac{q\delta_{k}-1}% {q-1}\Big\rparen^{\frac{1}{k-2}}\nobreak\ \leq\nobreak\ \max_{\varphi}% \operatorname{agr}(f,\varphi)\pm O(q^{-n})\nobreak\ \leq\nobreak\ \frac{1}{q}+% \big\lparen\frac{q-1}{q}\big\rparen\Big\lparen\frac{q\delta_{k}-1}{q-1}\Big% \rparen^{\frac{1}{k}}.

Proof.

The upper bound is a direct consequence of Corollary 26. For the lower bound, let $k\geq 3$ be an odd integer,

\max_{\varphi}\widetilde{\operatorname{agr}}(f,\alpha)^{k-2}\cdot\sum_{\varphi% }\widetilde{\operatorname{agr}}(f,\varphi)^{2}\nobreak\ \geq\nobreak\ \sum_{% \varphi}\widetilde{\operatorname{agr}}(f,\alpha)^{k}\nobreak\ \geq\nobreak\ % \frac{1}{q-1}(q\delta_{k}-1)\;.

Here, the second inequality follows from Corollary 26 and the test passing assumption. Thus, there exists a homomorphism $\varphi$ such that

\Big\lparen{\frac{q\cdot\operatorname{agr}{(f,\varphi)}-1}{q-1}}\Big\rparen^{k% -2}\nobreak\ \geq\nobreak\ \frac{1}{q-1}(q\delta_{k}-1)\;.\

Since $k-2$ is odd, this implies that we can take the positive $(k-2)^{\mathrm{th}}$ -root on either side of the inequality and obtain our result. $\hfill\blacktriangleleft$

4.2 Finite Field to Vector Space

Let, ${\mathbb{F}}_{q}$ be a finite field of order $q$ . Let, $G={\mathbb{F}}_{q}$ and $H={\mathbb{F}}^{n}_{q}$ . Let $f:G\rightarrow H$ be an arbitrary function. The set of homomorphisms, $\textup{Hom}(G,H)$ , have the property that for every non-trivial homomorphism $\varphi$ , $\ker(\varphi)=\{0\}$ . This property implies that no two homomorphisms agree on any non-zero input $x$ . We note a simple consequence of this below.

Observation 28.

Let $k\geq 1$ and $\vec{x}\in{\mathbb{F}}_{q}^{k}\setminus\{\vec{0}\}$ be a non-zero vector. Then, $\ker(\Gamma_{\vec{x}})=\{\mathrm{triv}\}$ .

Proof.

Let $x_{i}\neq 0$ be any non-zero element in the tuple, $\vec{x}$ . Then, for any non-trivial homomorphism $\varphi\in\textup{Hom}({\mathbb{F}}_{q},{\mathbb{F}}_{q}^{n})$ , $\varphi(x_{i})\neq 0$ and thus $\varphi\not\in\ker(\Gamma_{\vec{x}})$ . $\hfill\blacktriangleleft$

Recall the general version of the test which samples $\vec{x}\in G^{k}\propto\lvert\ker{\Gamma_{\vec{x}}}\rvert$ . This is problematic in our case as for $\vec{x}=0$ , we have $\lvert\ker{\Gamma_{\vec{0}}}\rvert=q^{n}$ , but $\ker(\Gamma_{\vec{x}})=1$ for every other vector $\vec{x}$ . We circumvent this issue by simply ignoring the $0$ element in $G$ and working over $\widetilde{G}={\mathbb{F}}_{q}^{*}$ , the set of non-zero elements of ${\mathbb{F}}_{q}$ . Accordingly, we will work with the fractional agreement of $f$ over $\tilde{G}$ ,

\widetilde{\operatorname{agr}}{(f,\varphi)}:=\mathchoice{\underset{x\sim% \widetilde{G}}{\mathbb{E}}\left[\mathds{1}_{f(x)=\varphi(x)}\right]}{{\mathbb{% E}}_{x\sim\widetilde{G}}[\mathds{1}_{f(x)=\varphi(x)}]}{{\mathbb{E}}_{x\sim% \widetilde{G}}[\mathds{1}_{f(x)=\varphi(x)}]}{{\mathbb{E}}_{x\sim\widetilde{G}% }[\mathds{1}_{f(x)=\varphi(x)}]}.

Using this modified agreement, $\widetilde{\operatorname{agr}}{(f,\varphi)}$ , we have the following claim.

Lemma 29 (A variant of Lemma 9).

Let $f:G\rightarrow H$ to be any function. Then, for any $k\geq 1$ ,

\sum_{\varphi\in\textup{Hom}({\mathbb{F}}_{q},{\mathbb{F}}_{q}^{n})}\widetilde% {\operatorname{agr}}{(f,\varphi)}^{k}\nobreak\ =\nobreak\ \mathchoice{% \underset{\vec{x}\sim\widetilde{G}^{k}}{\mathbb{E}}\left[\mathds{1}_{f(\vec{x}% )\in{\sf H}_{\vec{x}}}\right]}{{\mathbb{E}}_{\vec{x}\sim\widetilde{G}^{k}}[% \mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}]}{{\mathbb{E}}_{\vec{x}\sim% \widetilde{G}^{k}}[\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}]}{{\mathbb{E}}_% {\vec{x}\sim\widetilde{G}^{k}}[\mathds{1}_{f(\vec{x})\in{\sf H}_{\vec{x}}}]}.

Proof.

Identical to the proof of Lemma 9, after using Observation 28. $\hfill\blacktriangleleft$ The expression in Lemma 29 suggests the following simple test.

${\sf{Test\_NonZero}}_{k}(f)$

$\blacksquare$

Sample $\vec{x}\sim\widetilde{G}^{k}$ uniformly.
$\blacksquare$

If $f(\vec{x})\in{\sf H}_{\vec{x}}$ : return $1$ ; otherwise: return $0$ .
$\blacksquare$

Equivalently, the test passes only if $x_{i}^{-1}f(x_{i})=x_{j}^{-1}f(x_{j})$ for every $x_{i},x_{j}$ in the sampled tuple $\vec{x}$ .

Theorem 30.

Let $G={\mathbb{F}}_{q}$ some finite field of order $q$ and $H={\mathbb{F}}_{q}^{n}$ be a vector space. Let, $k\geq 2$ be any integer. Then if $f:G\rightarrow H$ passes ${\sf{Test\_NonZero}}_{k}(f)$ with probability $\delta_{k}$ , then,

\Big\lparen 1-\frac{1}{q}\Big\rparen\cdot\delta_{k}^{\frac{1}{k-1}}\nobreak\ % \leq\nobreak\ \max_{\varphi}\operatorname{agr}(f,\varphi)\nobreak\ \leq% \nobreak\ \frac{1}{q}+\Big\lparen\frac{q-1}{q}\Big\rparen\cdot\delta_{k}^{% \frac{1}{k}}\;\;.

Proof.

From the definition of the shifted agreement, we have, for any $\varphi$

\operatorname{agr}{(f,\varphi)}\nobreak\ \leq\nobreak\ \frac{1}{q}+\frac{q-1}{% q}\cdot\widetilde{\operatorname{agr}}{(f,\varphi)}.

Since, $\max_{\varphi}\widetilde{\operatorname{agr}}{(f,\varphi)}^{k}\nobreak\ \leq% \nobreak\ \sum_{\varphi}\widetilde{\operatorname{agr}}{(f,\varphi)}^{k}% \nobreak\ =\nobreak\ \delta_{k}$ , we get the upper bound. We have,

\max_{\varphi}\{\widetilde{\operatorname{agr}}(f,\varphi)^{k-1}\}\cdot\sum_{% \varphi}\widetilde{\operatorname{agr}}(f,\varphi)\nobreak\ \geq\nobreak\ \sum_% {\varphi}\widetilde{\operatorname{agr}}^{k}(f,\varphi)\nobreak\ =\nobreak\ % \delta_{k}\;.

From Lemma 29 for $k=1$ , we get $\sum_{\varphi}\widetilde{\operatorname{agr}}_{\varphi}\leq 1$ . Clearly, this quantity is greater than $0$ , as otherwise the above inequality forces $\delta_{k}=0$ for which the theorem trivially holds. Thus, we have the inequality,

\widetilde{\operatorname{agr}}{(f,\varphi)}\nobreak\ \geq\nobreak\ \delta_{k}^% {\frac{1}{k-1}}.

Finally, by rescaling we get or result:

\operatorname{agr}{(f,\varphi)}\nobreak\ \geq\nobreak\ \frac{|\tilde{G}|}{|G|}% \cdot\widetilde{\operatorname{agr}}{(f,\varphi)}\nobreak\ =\nobreak\ \Big% \lparen 1-\frac{1}{q}\Big\rparen\cdot\delta_{k}^{\frac{1}{k-1}}.\

$\hfill\blacktriangleleft$

5 Automorphism testing for Non-Abelian groups

We mention the main results of this section below. Please see the full version for the remainder of the section.

Theorem 31 (Testing $\textup{Aut}(D_{2p})$ ).

Let $G=D_{2p}$ be the dihedral group of order $2p$ for some prime $p>3$ . Let $k\geq 3$ be an integer, and $f:G\rightarrow G$ be any function. Then if $f$ passes ${\sf Test}\_{\sf Dihedral}_{k}$ with probability $\delta_{k}(f)$ , then there exists a automorphism $\varphi\in\textup{Aut}(G)$ such that $\operatorname{agr}(f,\varphi)\nobreak\ \geq\nobreak\ \frac{1}{2}\cdot\delta_{k% }(f)^{\frac{1}{k-2}}$ .

Theorem 32 (Restatement of Theorem 1.4).

The following results hold using ${\sf Test}\_{\sf Inner}_{k}$ :

$\blacksquare$

For any $n\neq 6$ , $\textup{Aut}(\textup{Sym}_{n})\,$ is $\Big\lparen k,\,\delta,\,\delta^{\frac{1}{k-2}}-o_{n}(1)\Big\rparen$ -testable for every $k\geq 3$ .
$\blacksquare$

For every non-abelian finite simple group $G$ , $\textup{Inn}(G)$ is $\Big\lparen k,\,\delta,\,\delta^{\frac{1}{k-5}}-o_{|G|}(1)\Big\rparen$ -testable for every $k\geq 6$ .
$\blacksquare$

For any exstraspecial group $G$ of order $p^{r}$ , $\textup{Inn}(G)$ is $\Big\lparen k,\,\delta,\,\delta^{\frac{1}{k-r}}-o_{p}(1)\Big\rparen$ -testable for every $k\geq r+1$ . In particular, for the family of Heisenberg groups over ${\mathbb{F}}_{p}$ , $H_{p}$ , $\textup{Inn}(H_{p})$ is $\Big\lparen k,\,\delta,\,\delta^{\frac{1}{k-3}}-o_{p}(1)\Big\rparen$ -testable for any $k\geq 4$ .
$\blacksquare$

Alternatively, if $p=O(1)$ is fixed and $r\rightarrow\infty$ , then we have that $\textup{Inn}(G)$ is $\Big\lparen k,\,\delta,\,\frac{1}{p}\delta^{\frac{1}{k-1}}\Big\rparen$ -testable for every $k\geq 2$ , and $r\geq 3$ .

Additionally, we get an upper bound of $\max_{\varphi}\operatorname{agr}{(f,\varphi)}\leq 2\delta^{\frac{1}{k}}$ , for any group $G$ and $k$ as above.

6 Lifting Homomorphism Tests

We mention the main results of this section below. Please see the full version for the remainder of the section.

Theorem 33 (Character Testing for $\mathrm{GL}_{n}(q)$ ).

Let $G=\mathrm{GL}_{n}(q)$ be the group of inverible $n\times n$ matrices over ${\mathbb{F}}_{q}$ for $q>2,n\geq 2$ . Let $f:G\rightarrow{\mathbb{F}}_{q}^{*}$ be any function and fix an integer $k\geq 4$ . Then if $f$ passes ${\sf Test}_{k}$ with probability $\delta_{k}$ , there exists a character $\varphi\in\textup{Hom}(\mathrm{GL}_{n}(q),{\mathbb{F}}_{q}^{*})$ such that $\operatorname{agr}(f,\varphi)\nobreak\ \geq\nobreak\ \big\lparen\zeta(2)^{2}% \cdot\delta_{k}\big\rparen^{\frac{1}{k-3}}$ .

Theorem 34.

For any $k\geq 3$ , ${\sf Test}\_\mathsf{LiftedVSpace}_{k}$ is a $(k,\delta,\varepsilon(\delta))$ sound test for $\textup{Hom}(G,{\mathbb{F}}_{p})$ for any finite group $G$ and prime $p$ , and for $\textup{LieHom}(\mathfrak{g},{\mathbb{F}}_{q})$ for any finite-dimensional Lie algebra, $\mathfrak{g}$ , and prime power $q$ .

Theorem 35 (Character Testing for $\mathfrak{gl}_{n}(q)$ ).

Let $q$ be a power of a prime $p$ , and let $\mathfrak{g}=\mathfrak{gl}_{n}(q)={\mathbb{F}}_{q}^{n\times n}$ , be the space of $n\times n$ -matrices. Let $k\geq 3$ be an integer. Let $f:\mathfrak{g}\rightarrow{\mathbb{F}}_{q}$ be any function. If $f$ passes ${\sf Test}_{k}(G,H,\mathcal{D}_{k})$ with probability $\delta_{k}$ , then,

\max_{\varphi\in\textup{Hom}(\mathfrak{g},{\mathbb{F}}_{q})}\operatorname{agr}% (f,\varphi)\nobreak\ \geq\nobreak\ \Big\lparen\frac{(p-1)^{2}}{p^{2}}\cdot% \delta_{k}\Big\rparen^{\frac{1}{k-1}}.

References

[1] László Babai, Katalin Friedl, and András Lukács. Near representations of finite groups, 2003. Manuscript.
[2] M. Bellare, D. Coppersmith, J. Håstad, M. Kiwi, and M. Sudan. Linearity testing in characteristic two. In Proceedings of the 36th IEEE Symposium on Foundations of Computer Science, pages 432–441, 1995.
[3] Michael Ben-Or, Don Coppersmith, Mike Luby, and Ronitt Rubinfeld. Non-Abelian homomorphism testing, and distributions close to their self-convolutions. Random Structures & Algorithms, 32(1):49–70, August 2007. doi:10.1002/rsa.20182.
[4] Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, and Avi Wigderson. Randomness-efficient low degree tests and short PCPs via $\varepsilon$ -biased sets. In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 612–621, 2003. doi:10.1145/780542.780631.
[5] Amey Bhangale and Subhash Khot. Optimal inapproximability of satisfiable k-LIN over non-abelian groups. In Proceedings of the 53rd ACM Symposium on Theory of Computing, 2021. doi:10.1145/3406325.3451003.
[6] M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. In Proceedings of the 22nd ACM Symposium on Theory of Computing, pages 73–83, 1990. doi:10.1145/100216.100225.
[7] Robin Chapman. Image of a fixed element under a random endomorphism in an abelian group. MathOverflow, 2010. URL:https://mathoverflow.net/q/30378 (version: 2010-07-04).
[8] Irit Dinur, Elena Grigorescu, Swastik Kopparty, and Madhu Sudan. Decodability of group homomorphisms beyond the Johnson bound. In Proceedings of the 40th ACM Symposium on Theory of Computing, pages 275–284, 2008. doi:10.1145/1374376.1374418.
[9] Irit Dinur, Madhu Sudan, and Avi Wigderson. Robust local testability of tensor products of LDPC codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 304–315. Springer Berlin Heidelberg, 2006. doi:10.1007/11830924_29.
[10] Parikshit Gopalan. A Fourier-Analytic Approach to Reed-Muller Decoding. IEEE Trans. Inf. Theory, 59(11):7747–7760, 2013. doi:10.1109/TIT.2013.2274007.
[11] W. T. Gowers, Ben Green, Freddie Manners, and Terence Tao. On a conjecture of marton, 2023. arXiv:2311.05762.
[12] William Timothy Gowers and Omid Hatami. Inverse and stability theorems for approximate representations of finite groups. Sbornik: Mathematics, 208(12):1784, 2017. doi:10.1070/SM8872.
[13] Elena Grigorescu, Swastik Kopparty, and Madhu Sudan. Local decoding and testing for homomorphisms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 375–385. Springer, 2006. doi:10.1007/11830924_35.
[14] Alan Guo and Madhu Sudan. List Decoding Group Homomorphisms Between Supersolvable Groups. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), 2014. doi:10.4230/LIPIcs.APPROX-RANDOM.2014.737.
[15] Johan Håstad and Avi Wigderson. Simple analysis of graph tests for linearity and PCP. Random Structures & Algorithms, 22(2):139–160, 2003. doi:10.1002/rsa.10068.
[16] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP* = RE. Commun. ACM, 64(11):131–138, 2021. doi:10.1145/3485628.
[17] M. Kiwi. Algebraic testing and weight distributions of codes. Theoretical Computer Science, 299(1):81–106, 2003. doi:10.1016/S0304-3975(02)00816-2.
[18] Tushant Mittal and Sourya Roy. Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime, 2024. doi:10.48550/arXiv.2405.18998.
[19] Cristopher Moore and Alexander Russell. Approximate representations, approximate homomorphisms, and low-dimensional embeddings of groups. SIAM Journal on Discrete Mathematics, 29(1):182–197, 2015. doi:10.1137/140958578.
[20] Anand Natarajan and Thomas Vidick. A quantum linearity test for robustly verifying entanglement. In Proceedings of the 49th ACM Symposium on Theory of Computing, 2017. doi:10.1145/3055399.3055468.
[21] Kenta Oono and Yuichi Yoshida. Testing properties of functions on finite groups. Random Structures & Algorithms, 49(3):579–598, February 2016. doi:10.1002/rsa.20639.
[22] Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. Journal of Computer and System Sciences, 72(6):1012–1042, 2006. doi:10.1016/J.JCSS.2006.03.002.
[23] A. Samorodnitsky. Low-degree tests at large distances. In Proceedings of the 39th ACM Symposium on Theory of Computing, 2007.
[24] Tom Sanders. On the Bogolyubov-Ruzsa lemma. Analysis & PDE, 5(3), 2012. doi:10.2140/apde.2012.5.627.
[25] Irving E. Segal. The automorphisms of the symmetric group. Bull. Am. Math. Soc., 46:565, 1940. doi:10.1090/S0002-9904-1940-07261-1.

[bib.bib1] [1] László Babai, Katalin Friedl, and András Lukács. Near representations of finite groups, 2003. Manuscript.

[bib.bib2] [2] M. Bellare, D. Coppersmith, J. Håstad, M. Kiwi, and M. Sudan. Linearity testing in characteristic two. In Proceedings of the 36th IEEE Symposium on Foundations of Computer Science, pages 432–441, 1995.

[bib.bib3] [3] Michael Ben-Or, Don Coppersmith, Mike Luby, and Ronitt Rubinfeld. Non-Abelian homomorphism testing, and distributions close to their self-convolutions. Random Structures & Algorithms, 32(1):49–70, August 2007. doi:10.1002/rsa.20182.

[bib.bib4] [4] Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, and Avi Wigderson. Randomness-efficient low degree tests and short PCPs via $\varepsilon$ -biased sets. In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 612–621, 2003. doi:10.1145/780542.780631.

[bib.bib5] [5] Amey Bhangale and Subhash Khot. Optimal inapproximability of satisfiable k-LIN over non-abelian groups. In Proceedings of the 53rd ACM Symposium on Theory of Computing, 2021. doi:10.1145/3406325.3451003.

[bib.bib6] [6] M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. In Proceedings of the 22nd ACM Symposium on Theory of Computing, pages 73–83, 1990. doi:10.1145/100216.100225.

[bib.bib7] [7] Robin Chapman. Image of a fixed element under a random endomorphism in an abelian group. MathOverflow, 2010. URL:https://mathoverflow.net/q/30378 (version: 2010-07-04).

[bib.bib8] [8] Irit Dinur, Elena Grigorescu, Swastik Kopparty, and Madhu Sudan. Decodability of group homomorphisms beyond the Johnson bound. In Proceedings of the 40th ACM Symposium on Theory of Computing, pages 275–284, 2008. doi:10.1145/1374376.1374418.

[bib.bib9] [9] Irit Dinur, Madhu Sudan, and Avi Wigderson. Robust local testability of tensor products of LDPC codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 304–315. Springer Berlin Heidelberg, 2006. doi:10.1007/11830924_29.

[bib.bib10] [10] Parikshit Gopalan. A Fourier-Analytic Approach to Reed-Muller Decoding. IEEE Trans. Inf. Theory, 59(11):7747–7760, 2013. doi:10.1109/TIT.2013.2274007.

[bib.bib11] [11] W. T. Gowers, Ben Green, Freddie Manners, and Terence Tao. On a conjecture of marton, 2023. arXiv:2311.05762.

[bib.bib12] [12] William Timothy Gowers and Omid Hatami. Inverse and stability theorems for approximate representations of finite groups. Sbornik: Mathematics, 208(12):1784, 2017. doi:10.1070/SM8872.

[bib.bib13] [13] Elena Grigorescu, Swastik Kopparty, and Madhu Sudan. Local decoding and testing for homomorphisms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 375–385. Springer, 2006. doi:10.1007/11830924_35.

[bib.bib14] [14] Alan Guo and Madhu Sudan. List Decoding Group Homomorphisms Between Supersolvable Groups. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), 2014. doi:10.4230/LIPIcs.APPROX-RANDOM.2014.737.

[bib.bib15] [15] Johan Håstad and Avi Wigderson. Simple analysis of graph tests for linearity and PCP. Random Structures & Algorithms, 22(2):139–160, 2003. doi:10.1002/rsa.10068.

[bib.bib16] [16] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP* = RE. Commun. ACM, 64(11):131–138, 2021. doi:10.1145/3485628.

[bib.bib17] [17] M. Kiwi. Algebraic testing and weight distributions of codes. Theoretical Computer Science, 299(1):81–106, 2003. doi:10.1016/S0304-3975(02)00816-2.

[bib.bib18] [18] Tushant Mittal and Sourya Roy. Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime, 2024. doi:10.48550/arXiv.2405.18998.

[bib.bib19] [19] Cristopher Moore and Alexander Russell. Approximate representations, approximate homomorphisms, and low-dimensional embeddings of groups. SIAM Journal on Discrete Mathematics, 29(1):182–197, 2015. doi:10.1137/140958578.

[bib.bib20] [20] Anand Natarajan and Thomas Vidick. A quantum linearity test for robustly verifying entanglement. In Proceedings of the 49th ACM Symposium on Theory of Computing, 2017. doi:10.1145/3055399.3055468.

[bib.bib21] [21] Kenta Oono and Yuichi Yoshida. Testing properties of functions on finite groups. Random Structures & Algorithms, 49(3):579–598, February 2016. doi:10.1002/rsa.20639.

[bib.bib22] [22] Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. Journal of Computer and System Sciences, 72(6):1012–1042, 2006. doi:10.1016/J.JCSS.2006.03.002.

[bib.bib23] [23] A. Samorodnitsky. Low-degree tests at large distances. In Proceedings of the 39th ACM Symposium on Theory of Computing, 2007.

[bib.bib24] [24] Tom Sanders. On the Bogolyubov-Ruzsa lemma. Analysis & PDE, 5(3), 2012. doi:10.2140/apde.2012.5.627.

[bib.bib25] [25] Irving E. Segal. The automorphisms of the symmetric group. Bull. Am. Math. Soc., 46:565, 1940. doi:10.1090/S0002-9904-1940-07261-1.

A General Framework for Low Soundness Homomorphism Testing

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

Definition 1.

High Soundness Regime

Low Soundness Regime

Issues with BLR

1.1 Our Contribution

1.1.1 Homomorphism Testing

Theorem 2 (Summary of Homomorphism Testing).

Combinatorial List Decoding

Theorem 3 (List Decoding for Cyclic groups).

1.1.2 Automorphism Testing over Non-Abelian Groups

Theorem 4 (Automorphism Testing (Summary of Theorems 31 and 32)).

1.1.3 Lifting Homomorphism Tests

Lie algebra characters

Theorem 5 (Lifting results).

▶ Remark 6.

1.2 Technical Overview

The evaluation map

Analyzing and adjusting the test

1.3 Outline

1.4 Prelims

Fact 7 (p-components of Abelian groups).

Fact 8 (Cyclic Homomorphisms).

Proof.

Notation.

2 A General Test

Lemma 9 (Rewriting the agreement).

Proof.

General Test

Corollary 10 (Test passing Probability).

Claim 11.

Proof.

Summarizing the expressions

3 Cyclic Groups

3.1 Cyclic groups of prime power order to abelian groups of small rank

Observation 12.

Proof.

Bounding 𝜸𝒌

Lemma 13 (Cyclic to Abelian).

Proof.

Corollary 14.

Proof.

Theorem 15 (Testing prime power cyclic groups to Abelian groups of bounded rank).

Proof.

Theorem 16 (List Size Bound).

Proof.

3.2 Arbitrary Cyclic groups

Lemma 17 (Reduction to p-groups).

Proof.

Definition 18 (Riemann Zeta Function).

Proposition 19.

Proof.

Theorem 20 (Testing Hom⁢(ℤn,ℤm)).

Proof.

4 Vector space over finite fields

4.1 Vector space to Finite Field

A shifted variant of agreement

Refining the test

Definition 21 (A level-j distribution).

Claim 22.

Proof.

Claim 23.

Proof.

Analyzing the key expression

Claim 24.

Proof.

Defining the refined test

Analysis of the Test

$\blacktriangleright$ Remark 6.

Fact 7 ( $p$ -components of Abelian groups).

Bounding $\gamma_{k}$

Theorem 20 (Testing $\textup{Hom}({\mathbb{Z}}_{n},{\mathbb{Z}}_{m})$ ).

Definition 21 (A level- $j$ distribution).

Theorem 31 (Testing $\textup{Aut}(D_{2p})$ ).

Theorem 33 (Character Testing for $\mathrm{GL}_{n}(q)$ ).

Theorem 35 (Character Testing for $\mathfrak{gl}_{n}(q)$ ).