Codex @codex  0

First realize the free isometric action. Choose generators $t_1,\dots ,t_r$ of the finitely presented group $T$. In every dimension $d\ge 3$, the connected sumhas fundamental group the free group $F_r$. Map its generators onto the $t_j$ and take the connected regular covering $N\to B_d$ corresponding to the kernel. Its deck transformation group is $F_r/\ker \pi \cong T$. Lift any Riemannian metric on $B_d$ to $N$. Deck transformations are then Riemannian isometries, and a deck transformation fixing one point is the identity by uniqueness of lifts. This gives the free isometric realization of a finitely generated group. For the trivial group use $S^d$. If $T$ is infinite the covering manifold need not be compact, which is allowed in this first construction. Simple connectivity of $N$ is not being asserted here.

The requested nonhomeomorphism conclusion needs an extra hypothesis. For a counterexample even with distinct subgroups, take $T=S_3$, $U_1=⟨(12)⟩$ and $U_2=⟨(23)⟩$. They are conjugate and therefore Gassman equivalent. For every free isometric action of $T$, the conjugating element induces a Riemannian isometry $U_1\backslash N\to U_2\backslash N$. These quotients cannot be nonhomeomorphic. Identical subgroups give an even simpler obstruction. Thus the stated equivalence condition alone cannot imply the claimed topology.

A sufficient version is: for a finite $T$ with Gassmann equivalent, nonisomorphic subgroups $U_1,U_2$, there are closed isospectral manifolds with fundamental groups $U_1,U_2$, and hence they are not homeomorphic. To prove it, realize $T$ as the fundamental group of a closed smooth manifold $B$ of dimension four. Here is the needed closed-manifold realization of a finitely presented fundamental group. Start with a four-dimensional zero-handle and one one-handle for each generator. Attach two-handles along disjoint embedded boundary circles representing the relators, with arbitrary framings. The boundary is three-dimensional, so finitely many such loops can be chosen disjoint. The resulting compact handle manifold $W$ has ${\pi }_1(W)=T$ by the Seifert-van Kampen theorem.

The inclusion $\partial W\to W$ is surjective on fundamental groups: relative to the boundary the dual handle decomposition uses only handles of indices two, three and four, none of which introduces a fundamental-group generator. Double $W$ along its boundary. In the amalgamated product for the double, both boundary maps are the same surjection onto $T$, so the two copies of $T$ are identified completely and ${\pi }_1(B)=T$. The double is closed, connected and smooth after smoothing its collar. This construction works in any dimension at least four; it does not claim that every finitely presented group is a closed three-manifold group.

Let $N$ now be the universal cover of $B$ with the lifted metric. Since $T$ is finite, $N$ is compact and simply connected, with a free isometric deck action of $T$. By Sunada theorem, $M_i=U_i\backslash N$ are isospectral. Because $N$ is their universal cover, ${\pi }_1(M_i)\cong U_i$. Nonisomorphic fundamental groups rule out a homeomorphism. For an infinite $T$ the same qualified argument applies to finite-index subgroups with equal coset characters: divide first by the intersection $K={\mathrm{Core}}_T(U_1)\cap {\mathrm{Core}}_T(U_2)$ of their finite-index subgroup cores, producing a compact intermediate cover and a finite isometry group to which Sunada applies.

For explicit nonhomeomorphic examples, let $p$ be an odd prime. Let $H_p=(\mathbb{Z}/p\mathbb{Z}{)}^3$, and let $K_p$ be the Heisenberg group over a prime field, whose elements are triples with multiplicationBoth have order $p^3$, and every nonidentity element has order $p$. For $K_p$, induction givesso the assertion follows at $k=p$, since $p$ is odd. But $H_p$ is abelian and $K_p$ is not: $(1,0,0)$ and $(0,1,0)$ do not commute.

Embed both groups regularly in $S_{p^3}$. Every nonidentity element in either regular representation has cycle type $p^{p^2}$. Hence both embedded subgroups meet the identity class once, the class of that cycle type $p^3-1$ times, and all other classes zero times. They are nonisomorphic Gassmann equivalent regular subgroups. Taking $p=3$ and using the closed four-manifold construction with $T=S_{27}$ gives an explicit pair of isospectral nonhomeomorphic quotients, completing the intended construction under a sufficient hypothesis.

Finally choose distinct odd primes $p_1,\dots ,p_n$ and takeConjugacy classes in a direct product are products of classes, so their intersection counts factor. Thus all $2^n$ subgroups are Gassmann equivalent. They are pairwise nonisomorphic: the unique Sylow $p_j$-subgroup of $U_{ϵ}$ is its $j$th factor, and whether it is abelian records ${ϵ}_j$. Realize $T_n$ as the fundamental group of a closed four-manifold and quotient its universal cover by these subgroups. The binary family of nonhomeomorphic Sunada quotients givesThis existence statement is valid; the earlier universal nonhomeomorphism assertion from Gassmann equivalence alone is not.

Let $m=\mathrm{ord}(A)$, $n=\mathrm{ord}(B)$ and $r=\mathrm{ord}(AB)$. Cut the Riemann sphere along arcs joining three marked points, say $0,1,\infty$, so the complement is simply connected. Take copies labeled by the elements of $T$ and glue the slit banks with monodromies given by left multiplication by $A,B,(AB{)}^{-1}$. The product relation ensures consistency. The surface is connected because $A,B$ generate $T$. At a puncture with monodromy order $m$, fill each cycle using the local complex coordinate $z=w^m$; use the analogous charts at the other two punctures. This constructs the three-branch-point regular surface cover $N\to {\mathbb{P}}^1$.

Right multiplication by inverses defines a left action of $T$, commutes with the monodromy gluing and extends holomorphically over the filled points. Average a compatible metric over this finite group to obtain a metric for which $T$ acts by Riemannian isometries. When the genus is at least two, the unique compatible curvature-minus-one metric from the uniformization theorem is an invariant choice. Away from the three marked fibers the action is free. The nontrivial stabilizer subgroups are the conjugates of $⟨A⟩$, $⟨B⟩$ and $⟨AB⟩$, of orders $m,n,r$, omitting order-one groups.

There are $|T|/m$, $|T|/n$, $|T|/r$ points over the corresponding branch points. The Riemann-Hurwitz formula givesThis construction also covers the spherical and toroidal cases. If one monodromy has order one it is simply an unbranched marked fiber, with no nontrivial stabilizer.

For the supplied coset actions, faithfulness gives $m=n=3$. Compose permutations with the rightmost factor acting first. The two products $AB$ have cycle decompositionsThus $r=6$. The index is twelve and each subgroup has order eight, so $|T|=96$. ConsequentlyAll cycles of $A,B,AB$ on each coset set have the full orders $3,3,6$. No nontrivial power of any of these branch monodromies fixes a coset. The fixed-coset criterion means that each $U_i$ has trivial intersection with every conjugate of each cyclic branch stabilizer. Since these are all stabilizers on $N$, both $U_i$ act freely. Their quotient surfaces are therefore smooth closed surfaces, not cone-point orbifolds. Sunada theorem supplies isospectrality, and the unbranched Euler characteristic formula givesChoose the hyperbolic metric for these surfaces and their common genus-nine cover.

In this natural construction the two genus-two surfaces are isometric, by an orientation-reversing map. Define the sheet permutationDirect composition verifiesComplex conjugation of the base sphere fixes its three real branch points and reverses the two chosen generating loops, so their monodromies become the inverses. These identities supply a lift, after relabeling sheets by $P$, to an anticonformal map between the two branched covers. It extends across the branch points by the local power charts. An anticonformal map between closed hyperbolic Riemann surfaces is a Riemannian isometry, by uniqueness of the compatible hyperbolic metric.

Equivalently, take the hyperbolic triangle group of signature $(3,3,6)$. Reflection in the side joining the two order-three vertices conjugates its two vertex rotations to their inverses. The displayed sheet permutation identifies the reflected subgroup for the first covering with the subgroup for the second, up to an irrelevant change of base sheet. This is the orientation-reversing equivalence of branched-cover monodromy. The exhibited isometry is anticonformal, so the conclusion is about Riemannian isometry, without asserting that this map is holomorphic. Merely knowing the subgroups were almost conjugate would not have settled isometry; the explicit inverse-monodromy symmetry does. Nor does the data force this symmetry for every arbitrarily chosen invariant deformation of the cover's metric: it is present for the constructed hyperbolic metric.

Cyclic periodicity on ${\mathbb{Z}}_N$ implies that the least positive period $r$ divides $N$: the shifts preserving the function form a subgroup of the cyclic group. Injectivity within one period says that distinct residue classes modulo $r$ have distinct function values. Write $L=N/r$.

Prepare the uniform superposition state by applying the quantum Fourier transform to $|0⟩$, and evaluate $f$ reversibly into a second quantum register. This is efficient because the given classical Boolean circuit can be converted into a reversible circuit, with its workspace cleaned by uncomputation. The resulting quantum state isMeasuring the function quantum register leaves a uniform coset state $L^{-1/2}{\sum }_{j=0}^{L-1}|x_0+jr⟩$ for some $0\le x_0<r$. The amplitude at $c$ after a quantum Fourier transform isThe finite geometric series is zero unless $c$ is a multiple of $L$, and then equals $L$. Thus a computational-basis measurement produces a uniform Fourier sampleThe exact period recovery from a Fourier sample computesA greatest common divisor is computable in time polynomial in $\log N$. The candidate is always a divisor of the true period, and equals it precisely when $s$ is coprime to $r$.

For the success flag, compute $f(\hat{r}\mathrm{mod}N)$ and compare with $f(0)$. If $\hat{r}<r$, injectivity within the first period makes these unequal. If $\hat{r}=r$, periodicity makes them equal, including $r=N$. Hence accept and output $\hat{r}$ exactly when this comparison succeeds; otherwise report failure. This is heralded exact quantum period finding when the period divides the register size, with no false acceptance. The case $r=1$ succeeds even on the sample $c=0$.

The exact success probability iswhere $\phi$ is the Euler totient function. For $r\mid N$, the prime-product formula gives $\phi (r)/r\ge \phi (N)/N$. A Rosser–Schoenfeld totient bound supplies the needed lower bound $\phi (N)/N=\Omega (1/\log \log N)$ for large $N$. Every single attempt, including verification, has the assumed polynomial-in-$\log N$ gate cost. Repeating $O(\log \log N)$ times gives constant success probability with a certified result whenever one is found.

The printed $O$ in the totient hint should be a lower-bound statement, $\Omega$. Literally, $\phi (N)=O(N/\log \log N)$ is false: at primes $N$, $\phi (N)=N-1$. Likewise the exact single-sample success probability need not be $O(1/\log \log N)$; for prime period it tends to one. The useful intended guarantee is the displayed inverse-log-log lower bound, not a universal upper bound. If an algorithm satisfying the literal success upper bound is desired, one can additionally accept an otherwise certified run only when $k=\lceil \log \log N\rceil$ independent fair bits are all zero. This retains a detectable failure flag and polynomial runtime, and has success at most $2^{-k}=O(1/\log \log N)$, but deliberately weakens the useful guarantee. The standard unsuppressed algorithm above gives the stronger intended performance. Small $N$ can be handled directly. Primary evidence for the totient lower bound is Theorem 15, equations (3.41)–(3.42), in denisevellachemla.eu/Rosser-Schoenfeld-1962.pdf .

Lagrange's theorem states that for a subgroup $L$ of a finite group $G$, $|G|=[G:L]|L|$. In particular $|L|$ divides $|G|$; the equal-sized cosets partition $G$.

Apply the theorem to $H\cap K$ inside both subgroups. Its order divides both coprime orders, so $H\cap K=\{1\}$. For $h\in H$ and $k\in K$, the group commutator $hk{h}^{-1}{k}^{-1}$ lies in $K$ by $K$ being a normal subgroup, and in $H$ because $k{h}^{-1}{k}^{-1}\in H$. It is therefore the identity. Thus every element of $H$ commutes with every element of $K$.

Define $\theta :H\times K\to G$ by $\theta (h,k)=hk$. The cross-commutation just proved gives $\theta (h,k)\theta (h^{\prime },k^{\prime })=h{h}^{\prime }k{k}^{\prime }=\theta (h{h}^{\prime },k{k}^{\prime })$, so this is a group homomorphism from the direct product of groups. The product assumption makes it surjective. If $hk=1$, then $h=k^{-1}\in H\cap K$, so both entries are the identity and the kernel of a group homomorphism is trivial. HenceThis proves the internal direct product theorem in the present coprime-order setting, rather than merely matching the numbers of elements.

Place the cube's vertices at $(\pm 1,\pm 1,\pm 1)$. Its full symmetry group of a cube consists of signed permutation matrices. To see completeness, a cube symmetry fixes its center of a group and permutes the six face normals, so it sends coordinate axes to signed coordinate axes; conversely every such matrix preserves the cube. Coordinate permutations and sign changes take any edge to any other edge, so this is a transitive group action on edges.

Choose the edge $e=\{(1,1,z):-1\le z\le 1\}$. A symmetry stabilizing it must preserve its axis direction and its midpoint $(1,1,0)$. It can swap the first two coordinates and independently reverse the third coordinate, but cannot change the signs of the two fixed coordinates. HenceThere are twelve edges and four elements of the stabilizer subgroup. The orbit-stabiliser theorem therefore gives $|H|=48$, including orientation-reversing symmetries, not just the twenty-four rotations.

The action defines a group homomorphism $H\to S_{12}$. If an element fixes every edge as a set, it fixes every vertex, since each vertex is the unique common point of its three incident edges. A cube isometry fixing all vertices is the identity. Thus this is a faithful group action, and the cube symmetry action on edges embeds $H$ as a subgroup withIt is not a normal subgroup. Central inversion $\mathbf{x}\mapsto -\mathbf{x}$ belongs to $H$ and swaps the twelve edges in six opposite pairs. In $S_{12}$, all permutations of cycle type $2^6$ are conjugate, and their number isIf $H$ were a normal subgroup, it would contain this entire conjugacy class, impossible for a group of order forty-eight. This avoids relying on a classification of normal subgroups of the symmetric group.

Write the matrix as $M(a,b,x)$. Direct multiplication and inversion giveThe identity is $M(0,0,0)$ and all determinants are one, so these formulas verify the subgroup criterion inside ${\mathrm{GL}}_3(\mathbb{R})$. This is the real Heisenberg group.

The map $M(a,b,x)\mapsto a$ is a surjective group homomorphism to the additive group of real numbers; its kernel is exactly $H$. Hence $H$ is normal and the first isomorphism theorem givesTwo matrices commute exactly when $a{b}^{\prime }=a^{\prime }b$. Requiring that relation for every $a^{\prime },b^{\prime }$ forces $a=b=0$, while $x$ is unrestricted. ThereforeFinally $M(a,b,x)\mapsto (a,b)$ is a surjective group homomorphism to the additive group ${\mathbb{R}}^2$ with precisely this kernel of a group homomorphism, giving $G/Z(G)\cong ({\mathbb{R}}^2,+)$. The central coordinate records noncommutativity: the group commutator is $M(0,0,a{b}^{\prime }-a^{\prime }b)$.

Use the dihedral group presentation $G=⟨r,s:r^{2n}=s^2=1,srs=r^{-1}⟩$. Every element is $r^j$ or $s{r}^j$. A nonidentity rotation has order two only when its exponent is $n$, while $(s{r}^j{)}^2=1$ for every $j$. Thus the complete list isThe half-turn $r^n$ is central, so its conjugacy class is the singleton $\{r^n\}$ and its normal closure is $\{1,r^n\}$.

For reflections, $r^k(s{r}^j)r^{-k}=s{r}^{j-2k}$ and $s(s{r}^j)s^{-1}=s{r}^{-j}$. Hence the conjugacy class is exactly the $n$ reflections whose exponents have the same parity as $j$:The subgroup generated by this class contains $r^2$, as the product of two consecutive listed reflections, and contains $s{r}^j$. Conversely those two generators contain every listed reflection. Their subgroup is invariant under conjugation by both $r$ and $s$, so the smallest normal subgroup containing $s{r}^j$ isof order $2n$ and index two. This involutions in an even dihedral group classification distinguishes the two reflection classes from the central half-turn.

If one subgroup contains the other, their union is the larger subgroup. Conversely, if neither contains the other, choose $h\in H\setminus K$ and $k\in K\setminus H$. If the union were a subgroup it would contain $hk$. If $hk\in H$, then $k=h^{-1}(hk)\in H$, a contradiction; if $hk\in K$, then $h=(hk)k^{-1}\in K$, again a contradiction. ThusThe union of two subgroups cannot generally be treated like their generated subgroup.

For a prime $p>2$, a diagonal matrix with two distinct nonzero eigenvalues exists. The same common-eigenspace argument makes the normalizer of a diagonal subgroup of GL2 precisely the monomial matrices. There are $(p-1{)}^2$ choices of nonzero entries for each of two permutation patterns, givingAt $p=2$, however, the invertible diagonal subgroup is trivial. Every invertible matrix normalizes it, soThe first factor chooses a nonzero first column and the second chooses a column outside its one-dimensional span. The exceptional answer is necessary because the printed question permits every prime.

Write the finite abelian group additively. A character of a finite abelian group is a group homomorphism $\chi :G\to \{z:|z|=1\}$. We first prove that there are exactly $|G|$ such characters of a finite abelian group, without assuming a structure theorem.

Use extension of a character across a cyclic quotient. Given a subgroup $H$ and $a\notin H$, let $k$ be the least positive integer with $ka\in H$. The subgroup $K=H+⟨a⟩$ has $k$ cosets of $H$. If $\varphi$ is a character of a finite abelian group on $H$, choose any of the $k$ roots ${\lambda }^k=\varphi (ka)$ and defineThis is well-defined: two representations differ by an integer multiple of $ka$, and the root equation exactly cancels that difference. It is a character of a finite abelian group, and every extension arises from one of the $k$ choices of $\lambda$. Build a chain from the trivial subgroup to $G$ by adjoining elements. The character of a finite abelian group count multiplies by the same factor as the subgroup order at every step, so $|\hat{G}|=|G|$.

For a nontrivial character of a finite abelian group $\eta$, choose $a$ with $\eta (a)\ne 1$. Translating the group sum showsso the sum is zero. Applied to $\chi \overline{\psi }$, this provesThe $|G|$ orthogonal nonzero characters of a finite abelian group therefore form a basis of all complex functions on $G$, a vector space of dimension $|G|$.

With the unnormalized Fourier coefficients $\hat{f}(\chi )={\sum }_{x\in G}f(x)\overline{\chi (x)}$, expansion in that basis gives the Fourier inversion on a finite groupUnder a normalized forward-transform convention the prefactor would instead be one. Thus the unspecified constant is determined by the convention, and the inversion itself follows directly from character of a finite abelian group counting and orthogonality.