On number of cyclic $n$-roots and disjointness of Fourier supports

Technical Summary: On the Number of Cyclic n-Roots and Disjointness of Fourier Supports

Problem Statement
The paper addresses the finiteness of the set of cyclic $n$-roots, which are $n$-dimensional complex vectors solving a specific system of multivariate homogeneous polynomial equations. A central conjecture by Björck and Saffari posits that the set of cyclic $n$-roots is finite if and only if $n$ is square-free. While the "only if" direction (infinite set if $n$ is not square-free) is established, and the "if" direction is proven for prime $n$ by Haagerup, the case for square-free composite $n$ remains open.

Haagerup's proof for prime $n$ relies on a critical reduction (Proposition 1): if the set of cyclic $n$-roots were infinite, there would exist two non-zero vectors $u, v \in \mathbb{C}^n$ such that their supports are disjoint in both the time domain and the frequency domain (specifically, $u_i v_i = 0$ and $\hat{u}_i \check{v}_i = 0$ for all $i$). For prime $n$, the additive uncertainty principle prevents such a pair from existing, thereby proving finiteness. The paper investigates whether this reduction holds for composite $n$, specifically asking if such disjoint-support pairs exist when $n$ is composite.

Methodology
The author employs Fourier analysis on finite cyclic groups $\mathbb{Z}_n$ to construct explicit counterexamples to the reduction step for composite $n$. The methodology involves:

1. Algebraic Construction: Utilizing subgroups of $\mathbb{Z}_n$ and their orthogonal complements. The paper leverages the Poisson summation formula analog for finite groups, specifically the relation $\widehat{\mathbf{1}_{H_d}} = \frac{d}{\sqrt{n}} \mathbf{1}_{H_d^\perp}$, where $H_d$ is a subgroup of order $d$.
2. Vector Synthesis: Constructing vectors $u$ and $v$ as linear combinations of characteristic functions of specific cosets and subgroups. The construction ensures that the support of $u$ is disjoint from the support of $v$ in the time domain, and the support of the Fourier transform of $u$ is disjoint from the support of the inverse Fourier transform of $v$.
3. Case Analysis:
   • Proposition 2: Constructs such pairs for $n = pqr$ (product of three mutually coprime integers) using translations of subgroups to cancel intersections.
   • Theorem 1: Generalizes the construction for any composite $n$. If $d$ is a divisor of $n$ such that $1 < d < \sqrt{2n}$, the author constructs a set of $1 + \lfloor d/2 \rfloor$ vectors that mutually satisfy the disjointness condition.
   • Single Vector Case (Proposition 3): Investigates the existence of a single vector $x$ where $\text{supp}(x) \cap \text{supp}(\hat{x}) = \emptyset$. This is linked to the existence of singular principal submatrices of the Fourier matrix. The author provides constructions for prime powers and specific composite cases, contrasting with the Chebotarëv theorem which guarantees non-vanishing minors for prime $n$.

Key Contributions and Results

• Theorem 1: The paper proves that a pair of non-zero vectors $u, v$ satisfying the disjoint support condition (Eq. 2) exists if and only if $n$ is composite.
  • If $n$ is composite: The author explicitly constructs such vectors. For a divisor $d$ of $n$ ($1 < d < \sqrt{2n}$), there exist at least $1 + \lfloor d/2 \rfloor$ mutually disjoint vectors satisfying the condition.
  • If $n$ is prime: The non-existence of such pairs is reaffirmed via the additive uncertainty principle, consistent with Haagerup's proof.
• Refutation of Reduction Adequacy: The primary result demonstrates that the reduction step used by Haagerup (Proposition 1) is not adequate for proving the finiteness of cyclic $n$-roots when $n$ is a square-free composite number. Since the "obstruction" (the existence of disjoint support pairs) exists for all composite $n$, the non-existence of such pairs cannot be used to prove finiteness for square-free composites.
• Concrete Examples: The paper provides explicit examples for $n=30$ and $n=6$. For $n=6$, it shows that while such disjoint pairs exist (satisfying the condition that would imply infinity if the reduction were sufficient), the set of cyclic 6-roots is known to be finite. This confirms that the existence of the pair is a necessary condition for the reduction to work, but not a sufficient condition to imply the infinity of cyclic roots.
• Extension of Conjectures: The paper discusses the existence of a single vector with disjoint time-frequency support. It connects this to the singularity of principal minors of the Fourier matrix. It supports the extension of the Chebotarëv theorem conjecture (that principal minors are non-vanishing for square-free $n$) by showing that such vectors exist for non-square-free $n$ (specifically prime powers and certain composite structures).

Significance and Claims
The paper claims modestly that its main contribution is identifying a bottleneck in the existing proof strategy for the Björck-Saffari conjecture.

• Clarification of the Reduction: It clarifies that Haagerup's reduction, which successfully proves finiteness for prime $n$, fails to distinguish between square-free composites and non-square-free composites because the "disjoint support" obstruction exists for all composite $n$.
• Implication for the Conjecture: The existence of these vector pairs for square-free composites implies that a new approach is required to prove the finiteness of cyclic $n$-roots for square-free composite $n$. The paper does not prove the conjecture true or false for these cases but demonstrates that the specific algebraic-geometric reduction used for primes is insufficient.
• Structural Insight: The work provides a deeper structural understanding of the relationship between cyclic $n$-roots, CAZAC sequences, and the spectral properties of the Fourier matrix, specifically regarding the singularity of its submatrices and the uncertainty principle in finite groups.

In summary, the paper establishes that the "disjoint Fourier support" phenomenon is a universal feature of composite dimensions, thereby invalidating the specific reduction argument used for primes as a general proof mechanism for the finiteness of cyclic $n$-roots in the square-free composite case.