New Bounds for Circular Trace Reconstruction

Our main technical tool is a family of shift-invariant functions which we call cyclic statistics. At a high level, a cyclic statistic of a sequence $x=(x_1,\mathrm{\dots },x_k)$ is a cyclically-invariant polynomial of the variables $x_1,\mathrm{\dots },x_k$; the statistic is obtained by summing a monomial function over all cyclic shifts of $x$. The order of this statistic is the degree of the corresponding monomial. If two strings $x$ and $y$ are cyclic shifts of each other, their cyclic statistics are clearly identical. Surprisingly, we prove that the converse holds for order $6$: if $x$ and $y$ are cyclically distinct, there exists a cyclic statistic of order $\le 6$ in which they differ. We give a lower bound showing that this result is nearly tight.

We prove the upper bound in Lemma 1 using Fourier techniques (see Lemma 19 in Section 3). We show that if $x$ and $y$ have identical cyclic statistics up to order $6$, their Fourier transforms $\widehat{x}$ and $\widehat{y}$ must satisfy a certain system of sparse linear equations, each involving $6$ or fewer variables. We then analyze this system and show that any solution $\widehat{x},\widehat{y}$ has the property that there exists an integer $c$ for which

By basic properties of Fourier transforms, this implies that $y$ is a cyclic shift of $x$.

The significance of the order $6$ stems from a number theoretic result. Our original constraints involve an equation of two variables for each $j\in [k]$, but our analysis only applies for $j$ relatively prime to $k$. We show that each $j\in [k]$ can be written as the sum of 2 or 3 integers relatively prime to $k$, transforming our constraint into a 6-variable equation, which implies Equation 1, given all cyclic statistics up to order 6 vanish.

The lower bound – that there exist $x$ and $y$ with identical cyclic statistics up to order 4 – is proved directly. We provide a pair of sequences of length 12 satisfying this property, obtained via computer search: $x_{(j)}=(0,2,3,2,1,1,1,1,2,3,2,0)$ and the sequence $y_{(j)}=3-x_{(j)}$.

Cyclic statistics are preserved in expectation by the cyclic deletion channel, leading to our algorithmic results. They also characterize the distribution of traces obtained from the deletion channel, from which we obtain our information-theoretic lower bound. We give a brief overview of this connection and our results below.

In order to build our lower bound, we relate the probability distribution over traces of $x$ to the cyclic statistics of $(x_1,\mathrm{\dots },x_k)$. Roughly, we show that the probability of generating a trace $\tilde{x}$ from $x$ can be expressed as a polynomial in $n$ of degree $L$ whose degree $L-m$ coefficient depends only on the order $m$ cyclic statistics of $x$. We use this fact to show that if two cyclically distinct strings $x$ and $y$ have identical cyclic statistics up to order $m$, the Hellinger distance between the distributions of the traces generated from $x$ and $y$ is $\tilde{O}(n^{-m-1})$. Therefore, it requires $\tilde{\mathrm{\Omega }}(n^{m+1})$ samples to distinguish the two distributions.

By Lemma 1, there exist two cyclically distinct sequences $x$ and $y$ with identical cyclic statistics up to order $4$. Plugging the corresponding strings into Theorem 2, we obtain our $\tilde{\mathrm{\Omega }}(n^5)$ lower bound for circular trace reconstruction.

We build an algorithm that can recover any $k$-sparse string $x$ using $\tilde{O}(n^6)$ samples from the deletion channel, showing that our techniques from above cannot be extended to yield a significantly stronger lower bound.

As explained above, our algorithm exploits the fact that the retention probability $q≔1-p$ is a constant. Therefore, with constant probability, no 1 is deleted in $x$. Conditioning on this, every trace $\tilde{x}$ can be expressed as a sequence of binomial random variables; that is, $\tilde{x}=({\tilde{x}}_1,\mathrm{\dots },{\tilde{x}}_k)$ with ${\tilde{x}}_j\sim \text{Bin}(x_j,q)$. By Lemma 1, any two cyclically distinct sequences $x$ and $y$ differ in some cyclic statistic of order at most $6$. As all cyclic statistics of integer sequences are integers, the difference between $x$ and $y$ in this statistic is at least $1$. Thus we aim to estimate cyclic statistics from traces to within constant error.

A naïve estimator is the empirical average of a certain cyclic statistic of the traces. However, this naïve algorithm requires $\mathrm{\Omega }(n^{11})$ samples. This is because, in the worst case, each ${\tilde{x}}_j$ may have mean and variance both $\mathrm{\Omega }(n)$. Thus the variance of the product of $6$ such random variables may be $\mathrm{\Omega }(n^{11})$. However, instead, if we can shift the binomials such that they become random variables whose absolute value is $\tilde{O}(\sqrt{n})$, the absolute value of their product will be bounded by $\tilde{O}(n^3)$ leading to variance $\tilde{O}(n^6)$. We accomplish this by greedily partitioning the set of expected gaps $\{q{x}_j\}$ into clusters, so that all elements in the same cluster are $\tilde{O}(\sqrt{n})$-close to each other and $\tilde{\mathrm{\Omega }}(\sqrt{n})$-far from all other clusters. Since each binomial is tightly concentrated around its expectation, we can map each ${\tilde{x}}_j$ to the correct cluster with high probability, and subtract the cluster center from ${\tilde{x}}_j$ to obtain a random variable whose absolute value is bounded by $\tilde{O}(\sqrt{n})$ with high probability.

A final hurdle is that subtracting cluster centers may erase any differences in the cyclic statistics of $x$ and $y$. See the discussion at the start of Section 4 and Example 22 for more algorithmic intuition, and discussion of why cyclic statistics mod $\mathrm{\ell }$ are needed to yield a $\tilde{O}(n^6)$ algorithm. See Algorithm 1 and Theorem 26 for our main algorithmic result.

Letting $j_2^{\prime }\equiv j_2-j_1\text{ mod }k\mathrm{\dots },j_m^{\prime }\equiv j_m-j_1\text{ mod }k$, and interpreting indices mod $k$:

where the exponential terms vanish in the second-to-last equality because $i_1+\mathrm{\cdots }+i_m\equiv 0\text{ mod }k$ and so $e^{\frac{2\pi i}{k}{j}_1{i}_1}\mathrm{\cdots }{e}^{\frac{2\pi i}{k}{j}_1{i}_m}=1$. Since $S_{0,j_2^{\prime },\mathrm{\dots },j_m^{\prime }}(x)=S_{0,j_2^{\prime },\mathrm{\dots },j_m^{\prime }}(y)$ for all $j_2^{\prime },\mathrm{\dots },j_m^{\prime }$ by assumption, we have that the corresponding $m$-way products of Fourier terms are equal. $◀$

Lemma 9 implies that for any $i_1,\mathrm{\dots },i_m$ satisfying $i_1+\mathrm{\cdots }+i_m\equiv 0\text{ mod }k$, if the Fourier coefficients ${\widehat{x}}_{i_1},\mathrm{\dots },{\widehat{x}}_{i_m}$ are nonzero, then ${\widehat{y}}_{i_1},\mathrm{\dots },{\widehat{y}}_{i_m}$ must be nonzero as well. We now partition the elements of $[k]$ into equivalence classes based on their gcd with $k$.

We show that for a single integer sequence $x$, the Fourier coefficients of $x$ in each $G_{\alpha }$ are either all zero or all nonzero, allowing us to analyze them together. This can be shown using a well-known property of cyclotomic fields: for every primitive $d$th root of unity of form ${\omega }_d=e^{2\pi i/d}$, the Galois group $\text{Gal}(\mathbb{Q}({\omega }_d)/\mathbb{Q})$ is isomorphic to ${(\mathbb{Z}/d\mathbb{Z})}^{\times }≔\{j\in \{0,\mathrm{\dots },d-1\}:\gcd (j,k)=1\}$, the multiplicative group of integers mod $d$. The isomorphism is specified by Fact 11.

Suppose ${\widehat{x}}_j=0$. Let $d≔\frac{k}{\alpha }$ and consider the a primitive $d$th root of unity ${\omega }_d≔e^{2\pi i/d}$. The $j$th Fourier coefficient of $x$ is given by

Let $z$ be a sequence of length $d$ generated by interpreting each index of $x$ mod $d$ and summing together all elements that map to a given location. (In other words, $z_j≔{\sum }_{\mathrm{\ell }:\mathrm{\ell }\equiv j\text{ mod }d}{x}_{\mathrm{\ell }}$.) Then the Fourier transform of $z$ at location $\frac{j}{\alpha }$ is given by

Similarly, ${\widehat{z}}_{j^{\prime }/\alpha }={\widehat{x}}_{j^{\prime }}$. Because $z$ is an integer sequence, ${\widehat{z}}_{j/\alpha }$ and ${\widehat{z}}_{j^{\prime }/\alpha }$ are elements of the cyclotomic field $\mathbb{Q}({\omega }_{d/\alpha })$. Choose $b\in {(\mathbb{Z}/d\mathbb{Z})}^{\times }$ such that $b\frac{j}{\alpha }\equiv \frac{j^{\prime }}{\alpha }\text{ mod }d$. By Fact 11, there exists ${\sigma }_b\in \text{Gal}(\mathbb{Q}({\omega }_d)/\mathbb{Q})$ such that ${\sigma }_b({\omega }_d)={\omega }_d^b$. Therefore, we have

as desired. $◀$

Consider two sequences $x$ and $y$ with identical second order cyclic statistics. As a simple consequence of Lemmas 9 and 12, $\widehat{x}$ and $\widehat{y}$ are jointly zero or jointly nonzero everywhere in the indices belonging to a single $G_{\alpha }$.

Suppose ${\widehat{x}}_j\ne 0$ for some $j\in G_{\alpha }$. By Lemma 12, we must have ${\widehat{x}}_{j^{\prime }}\ne 0$ for all $j^{\prime }\in G_{\alpha }$. Note that $k-j\in G_{\alpha }$, so ${\widehat{x}}_{k-j}\ne 0$. Moreover, $j+(k-j)\equiv 0\text{ mod }k$, so by Lemma 9, we have ${\widehat{y}}_j\cdot {\widehat{y}}_{k-j}={\widehat{x}}_j\cdot {\widehat{x}}_{k-j}\ne 0$. This requires that ${\widehat{y}}_j\ne 0$. Applying Lemma 12 to $y$, we have that $\widehat{y}$ is nonzero for all indices in $G_{\alpha }$, proving the first statement.

If $x_j=0$, then similarly ${\widehat{y}}_j\cdot {\widehat{y}}_{k-j}={\widehat{x}}_j\cdot {\widehat{x}}_{k-j}=0$, requiring that either ${\widehat{y}}_j=0$ or ${\widehat{y}}_{k-j}=0$. By Lemma 12, $\widehat{x}$ and $\widehat{y}$ must be zero everywhere in $G_{\alpha }$, proving the second statement. $◀$

First, consider the case in which $p\ne 2$. At least one of $j-1,j+1$ must be relatively prime to $p^a$ since their difference is 2, which itself is relatively prime to $p$. Since $j\equiv (j-1)+1\text{ mod }{p}^a$, $j\equiv (j+1)+(p^a-1)\text{ mod }{p}^a$, and both $1$ and $p^a-1$ are relatively prime to $p^a$, at least one of these two expressions expresses $j$ as the sum of 2 numbers both relatively prime to $p^a$. Similarly, at least one of $j-2,j+2$ must be relatively prime to $p^a$ since their difference is 4, which itself is relatively prime to $p$. Thus since $j\equiv (j-2)+1+1\text{ mod }{p}^a$ and $j\equiv (j+2)+(p^a-1)+(p^a-1)\text{ mod }{p}^a$, and since both $1$ and $p^a-1$ are relatively prime to $p^a$, at least one of these two expressions expresses $j$ as the sum of 3 numbers both relatively prime to $p^a$.

For the case of $p=2$, we note that if $j$ is even, then $j-1$ is relatively prime to $2^a$ and thus we express $j=(j-1)+1$. Otherwise, if $j$ is odd, then $j-2$ is relatively prime to $2^a$, and we express $j=(j-2)+1+1$. $◀$

Consider the prime factorization of $d$: $d=p_1^{a_1}\cdot \mathrm{\dots }\cdot p_{\mathrm{\ell }}^{a_{\mathrm{\ell }}}$. Given $j\in \mathbb{Z}/d\mathbb{Z}$, we use the Chinese remainder theorem to express $j$ via its residues mod $p_i^{a_i}$, for each prime factor $p_i$. Define $j_i≔j\text{ mod }{p}_i^{a_i}$. We note that $j$ is relatively prime to $d$ if and only if each $j_i$ is relatively prime to its corresponding prime power $p_i^{a_i}$.

We use Fact 14 (and the Chinese remainder theorem) to canonically represent each $j\in \mathbb{Z}/d\mathbb{Z}$ as the sum mod $d$ of either 2 or 3 numbers that are each relatively prime to $d$. If either $d$ is odd or $j$ and $d$ are both even, we represent $j$ as the sum of 2 numbers, by applying Fact 14 to represent each $j_i$ as $j_i\equiv b_i^{(1)}+b_i^{(2)}\text{ mod }{p}_i^{a_i}$ with $b_i^{(1)}$ and $b_i^{(2)}$ relatively prime to $p_i^{a_i}$. By the Chinese remainder theorem, the system, $b^{(1)}\equiv b_i^{(1)}\text{ mod }{p}_i^{a_i},\forall i\in [\mathrm{\ell }]$, has a unique solution $b^{(1)}$ relatively prime to $d$; similarly, there exists a unique $b^{(2)}$ relatively prime to $d$ satisfying $b^{(2)}\equiv b_i^{(2)}\text{ mod }{p}_i^{a_i}$ for all $i$. Finally, $b^{(1)}+b^{(2)}\equiv j\text{ mod }d$, which proves the first case. If $j$ is odd and $d$ is even, we use the analogous procedure to represent $j$ as the sum of 3 numbers relatively prime to $d$, which proves the second case. $◀$

Using the representation given by Lemma 15, we analyze the system of complex-valued linear equations described at the beginning of this subsection.

For all $j\in \mathbb{Z}/d\mathbb{Z}$, let $[[j]]$ denote the canonical representation of $j$ given by Lemma 15 as the sum mod $d$ of either 2 or 3 numbers relatively prime to $d$ (so $[[j]]$ is a set of size 2 or 3). Let $z_{[[j]]}$ denote the sum of the 2 or 3 corresponding variables. For convenience, we write the set $d-[[j]]≔\{d-j^{\prime }:j^{\prime }\in [[j]]\}$. Then the conditions of the lemma imply the following set of conditions:

To see the implication, it suffices to show that the left hand side of each constraint is a sum of at most 6 real variables whose indices are relatively prime to $d$. For all $j$ with $\gcd (j,d)=1$, we have $\gcd (d-j,d)=1$, so the first constraint satisfies the condition. For all $j$, $z_{[[j]]}$ can be written as a sum of 2 or 3 variables whose indices are relatively prime to $d$, so the second constraint requires at most 4 variables. Finally, if $d$ is odd, the representation $[[j]]$ comprises 2 variables for all $j$, in which case the third constraint requires 5 variables. If $d$ is even, the values $j$ and $j+1$ comprise 1 even number and 1 odd number, and $d-[[j+1]]$ has the same parity as $j+1$, resulting in at most 6 terms.

Note that these three sets of conditions collectively imply that $z_{[[j]]}+z_1-z_{[[j+1]]}\in \mathbb{Z}$ for all $j\in \mathbb{Z}/d\mathbb{Z}$. Therefore, any set of solutions $z_{[[j]]}$ must form an arithmetic sequence of increment $z_1$ plus some integer, i.e., $z_{[[j]]}-j{z}_1\in \mathbb{Z}$ for all $j$. Therefore, $d{z}_1\in \mathbb{Z}$, which requires that $z_1$ is a multiple of $\frac{1}{d}$ (and is therefore real). Writing $z_1=\frac{c}{d}$ for some integer $c$, we have $z_{[[j]]}\equiv \frac{cj}{d}\text{ mod }1$ for all $j\in \mathbb{Z}/d\mathbb{Z}$. Finally, the first and second conditions imply that $z_j=z_{[[j]]}$ for all $j$ relatively prime to $d$, which proves the lemma. $◀$

The following technical lemma is used in the proof of the main result of this section, Lemma 19. Intuitively, in the proof of Lemma 19 we aim to show that variables $z_0,\mathrm{\dots },z_{k-1}$ form an arithmetic sequence. Instead we show that, for each value $\alpha$, those $z_j$ with index $j$ satisfying $gcd(j,k)=\alpha$ form an arithmetic sequence of increment $c_{\alpha }$. We use the following lemma to show that this implies there is a consistent arithmetic sequence across all $j$, with some increment $c$.

Consider the prime factorization of $k$, $k=p_1^{a_1}\mathrm{\dots }{p}_{\mathrm{\ell }}^{a_{\mathrm{\ell }}}$. For each $i\in [\mathrm{\ell }]$, we will show there exists $c_i$ satisfying the desired property mod $p_i^{a_i}$, and conclude the lemma by the Chinese remainder theorem.

Fix $i\in [\mathrm{\ell }]$. Define ${\alpha }_i$ to be the element of $A$ with the lowest $p_i$-adic valuation: ${\alpha }_i={\arg \min }_{\alpha \in A}{\nu }_{p_i}(\alpha )$. Let $c_i$ be an integer satisfying $(c_i-c_{{\alpha }_i}){\alpha }_i\equiv 0\text{ mod }{p}_i^{a_i}$, and consider any ${\alpha }^{\prime }\in A$. By a well-known property of $p$-adic valuations, we have ${\nu }_{p_i}(\text{lcm}({\alpha }^{\prime },{\alpha }_i))=\max \{{\nu }_{p_i}({\alpha }^{\prime }),{\nu }_{p_i}({\alpha }_i)\}={\nu }_{p_i}({\alpha }^{\prime })$. The prime power $p_i^{{\nu }_{p_i}({\alpha }^{\prime })}$ divides ${\alpha }^{\prime }$, so it also divides $\text{lcm}({\alpha }^{\prime },{\alpha }_i)$. Therefore, we have the following two facts:

Using the fact that ${\nu }_{p_i}({\alpha }^{\prime })\ge {\nu }_{p_i}({\alpha }_i)$ to combine the two equations, we have $(c_i-c_{{\alpha }^{\prime }})p_i^{{\nu }_{p_i}({\alpha }^{\prime })}\equiv 0\text{ mod }{p}_i^{a_i}$. Finally, we multiply both sides by the integer ${\alpha }^{\prime }{p}_i^{-{\nu }_{p_i}({\alpha }^{\prime })}$ to yield $(c_i-c_{{\alpha }^{\prime }}){\alpha }^{\prime }\equiv 0\text{ mod }{p}_i^{a_i}$. Choosing $c_i=c_{{\alpha }_i}$ for all $i$, the equation above holds for all pairs $i,\alpha$. We now wish to find $c$ such that $c\equiv c_i\text{ mod }{p}_i^{a_i}$ for all $i$. Such an integer $c$ is guaranteed to exist by the Chinese remainder theorem, which completes the proof. $◀$

It suffices to show that there exists an integer $c$ such that ${\widehat{x}}_j={\widehat{y}}_j\cdot \exp \left(2\pi i\cdot \frac{cj}{k}\right)$ for all $j\in [k]$. By Lemma 13, this property holds for all $j$ where ${\widehat{x}}_j=0$. Therefore, we consider only the divisors $\alpha$ such that the Fourier coefficients are nonzero everywhere in $G_{\alpha }$ for both $x$ and $y$. For all $j$ with nonzero Fourier coefficients ${\widehat{x}}_j$ and ${\widehat{y}}_j$, define $z_j≔\frac{1}{2\pi i}\cdot \log \left(\frac{{\widehat{x}}_j}{{\widehat{y}}_j}\right)$, where $\log$ is the unique complex-valued function satisfying $e^{\log z}=z$ and $\text{Im}\log z\in (0,2\pi ]$ for all $z\in ℂ\backslash \{0\}$. To prove the lemma, we show that there exists an integer $c$ such that for all $j$ with ${\widehat{x}}_j\ne 0$ and ${\widehat{y}}_j\ne 0$, $\text{Im}{z}_j=0$ and $z_j\equiv \frac{cj}{k}\text{ mod }1$.

Fix $\alpha \in [k]$ and let $d≔\frac{k}{\alpha }$. Note that for all $j\in G_{\alpha }$, $\gcd (\frac{j}{\alpha },d)=1$. Therefore, each $j\in G_{\alpha }$ corresponds to a unique number relatively prime to $d$. Consider any $m$-tuple $j_1,\mathrm{\dots },j_m\in G_{\alpha }$ such that $\frac{j_1}{\alpha }+\mathrm{\dots }+\frac{j_m}{\alpha }\equiv 0\text{ mod }d$. By Lemma 9, we have $z_{j_1}+\mathrm{\dots }+z_{j_m}\in \mathbb{Z}$. Applying Lemma 16 (and using the fact that $k=d\alpha$), there exists an integer $c_{\alpha }$ such that for all $j\in G_{\alpha }$, we have $z_j-\frac{c_{\alpha }j}{k}\in \mathbb{Z}$. In other words, $z_j$ is real and $z_j\equiv \frac{c_{\alpha }j}{k}\text{ mod }1$.

We have shown that for all $G_{\alpha }$ with nonzero Fourier coefficients, we can write $k{z}_j\equiv c_{\alpha }j\text{ mod }k$. We will now show that this is true for a single consistent integer $c=c_{\alpha }$ across all $\alpha$. Consider $\alpha \ne {\alpha }^{\prime }$ where $\widehat{x}$ and $\widehat{y}$ are nonzero everywhere in $G_{\alpha }\cup G_{{\alpha }^{\prime }}$. Let $c_{\alpha },c_{{\alpha }^{\prime }}$ respectively be the corresponding coefficients, and $\mathrm{\ell }=\text{lcm}(\alpha ,{\alpha }^{\prime })$. Since $\mathrm{\ell }$ is a multiple of $\alpha$, Lemma 15 implies that we can write $\mathrm{\ell }/\alpha$ as a sum mod $k/\alpha$ of 2 or 3 numbers relatively prime to $k/\alpha$. Multiplying by $\alpha$, we can write $\mathrm{\ell }$ as a sum mod $k$ of 2 or 3 numbers whose gcd with $k$ is $\alpha$; denote this representation as $[[\mathrm{\ell }]]$. Since $\mathrm{\ell }$ is also a multiple of ${\alpha }^{\prime }$, it must also have a representation ${[[\mathrm{\ell }]]}^{\prime }$ as a sum mod $k$ of 2 or 3 numbers whose gcd with $k$ is ${\alpha }^{\prime }$.

We write $z_{[[\mathrm{\ell }]]}$ and $z_{[[{\mathrm{\ell }}^{\prime }]]}$ to denote the sum of the variables corresponding to the indices in $[[\mathrm{\ell }]]$ and $[[{\mathrm{\ell }}^{\prime }]]$ respectively, and use the convention that $k-[[\mathrm{\ell }]]=\{k-j:j\in [[\mathrm{\ell }]]\}$. Since $\frac{j}{\alpha }+\frac{k-j}{\alpha }\equiv 0\text{ mod }\frac{k}{\alpha }$ for all $j\in G_{\alpha }$, we have $z_{\mathrm{\ell }}+z_{k-[[\mathrm{\ell }]]}\equiv 0\text{ mod }1$ for all $\mathrm{\ell }$. From the previous paragraph, we have that the sum of the elements in $[[\mathrm{\ell }]]$ equals the sum of the elements in ${[[\mathrm{\ell }]]}^{\prime }$ mod $k$. We thus conclude the condition that $\mathrm{\ell }$ has a consistent coefficient in both representations, as $z_{[[\mathrm{\ell }]]}=z_{{[[\mathrm{\ell }]]}^{\prime }}$, and reexpress this as a sum of 4 to 6 coefficients, moving everything to the left-hand side, as $z_{[[\mathrm{\ell }]]}+z_{k-{[[\mathrm{\ell }]]}^{\prime }}\equiv 0\text{ mod }1$. Recall that $[[\mathrm{\ell }]]$ only contains indices $j$ with $\gcd (j,k)=\alpha$, and the corresponding variables $z_j$ satisfy $k{z}_j\equiv c_{\alpha }j\text{ mod }k$. Similarly, ${[[\mathrm{\ell }]]}^{\prime }$ only contains indices $j^{\prime }$ with $\gcd (j^{\prime },k)={\alpha }^{\prime }$, and each $z_{j^{\prime }}$ satisfies $k{z}_{j^{\prime }}\equiv c_{{\alpha }^{\prime }}{j}^{\prime }\text{ mod }k$. Therefore, the constraint $(c_{{\alpha }^{\prime }}-c_{\alpha })\mathrm{\ell }\equiv 0\text{ mod }k$ holds for any pair of $\alpha ,{\alpha }^{\prime }\in A\subseteq [k]$, where $A=\{\alpha :\widehat{x},\widehat{y}\text{ are nonzero everywhere in }{G}_{\alpha }\}$.