Proof. We prove (i); the proof of (ii) is the same argument with the inequalities reversed. To prove \(G\) is product-dominant, we must show \[\begin{aligned} \label{eq:mptq_prob_cond} P(d(A)>0) > P(d(A)<0) \end{aligned}\] where \(P\) denotes the probability over a uniformly chosen random subset \(A \subseteq G\). We use the shorthand \(P(d<0)\) and \(P(d>0)\). Let \(\mu_1\) be the expected value of \(d(A)\) and \(\sigma^2\) be the variance. Since \(M_1>0\) implies \(\mu_1>0\), Cantelli’s inequality gives \[\begin{aligned} P(d\leq 0)\ = P(d - \mu_1\leq -\mu_1)\ \leq\ \frac{\sigma^2}{\sigma^2 +\mu_1^2}. \end{aligned}\] Hence, \[\begin{aligned} P(d>0)\ =\ 1-P(d\leq 0)\ \geq\ 1-\frac{\sigma^2}{\sigma^2 + \mu_1^2}. \end{aligned}\] On the other hand, let \(\beta := P(d=0)=B/2^{|G|}\) be the proportion of balanced sets. Then, \[\begin{aligned} P(d<0)\ &=\ 1-P(d\geq 0)\ =\ 1-P(d=0)-P(d>0) \notag \\ &= 1-\beta-P(d>0) \leq 1- \beta -\left ( 1-\frac{\sigma^2}{\sigma^2 + \mu_1^2} \right ) \notag \\ &= \frac{\sigma^2}{\sigma^2 + \mu_1^2}-\beta. \end{aligned}\] Therefore, from [eq:mptq_prob_cond] we see \[\begin{aligned} \label{eq:probv1} 1-\frac{\sigma^2}{\sigma^2 + \mu_1^2} > \frac{\sigma^2}{\sigma^2 +\mu_1^2}-\beta \ \implies\ G \text{ is product-dominant}. \end{aligned}\]

we may simplify the expression in [eq:probv1] by using the fact that \(\sigma^2 + \mu_1^2 = \mu_2\) (see [statproofbookSecondMoment], for example). This gives \[\begin{aligned} 1-\frac{\sigma^2}{\sigma^2 + \mu_1^2}\ >\ \frac{\sigma^2}{\sigma^2 +\mu_1^2}-\beta \ &\iff\ 1+\beta\ >\ \frac{2 \sigma^2}{\sigma^2 + \mu_1^2} \notag \\ &\iff 1 +\beta \ >\ \frac{2\mu_2 - 2\mu_1^2}{\mu_2} \notag \\ &\iff \frac{2\mu_1^2}{\mu_2}\ >\ 1 -\beta \notag \\ &\iff \frac{2M_1^2}{M_2} \ >\ 2^{|G|} -B \notag \\ &\iff \frac{M_1^2}{(2^{|G|}-B)M_2} > \frac 12 \end{aligned}\] as claimed. ◻

Proof. Follows from [eq:exp_breakdown], [eq:prod_indep_id], and [eq:quot_indep_id]. ◻

Proof. For \(x \in G\), define \[\begin{aligned} q_g(x)\ :=\ q_g^{(1)}(x)\ :=\ g^{-1}x, \quad \quad &q_g^{(n)}(x)\ :=\ q_g(q_g^{(n-1)}(x)), \\ p_g(x)\ :=\ p_g^{(1)}(x)\ :=\ x^{-1}g, \quad \quad &p_g^{(n)}(x)\ :=\ p_g(p_g^{(n-1)}(x)). \end{aligned}\] Then, \(y=q_g(x)\) is the unique element satisfying \(xy^{-1}=g\), and similarly, \(y=p_g^{(1)}(x)\) is the unique element satisfying \(xy=g\). Thus, the forbiddance graph \(\mathcal F_Q(g)\) locally around \(x\) looks like \[x \to q_g^{(1)}(x) \to q_g^{(2)}(x) \to \cdots,\] and this path must eventually loop back around to \(x\), since \(q_g^{(1)}\) is a bijection and \(G\) is finite. The same holds for \(p_g^{(1)}\). It follows that both forbiddance graphs are composed of disjoint cycles. ◻

Proof. The claim follows by induction. The base case for \(q_g^{(1)}\) is by definition, and then \[\begin{aligned} q_g^{(n)}(x)\ =\ q_g^{(1)}(q_g^{(n-1)}(x))\ =\ g^{-1}(g^{-(n-1)}x)\ =\ g^{-n}x. \end{aligned}\] For \(p_g\), the base case \(p_g^{(1)}\) is by definition. Then, \[\begin{aligned} p_g^{(2n)}(x)\ &=\ p_g(p_g^{(2n-1)}(x))\ =\ p_g(g^{-n+1}x^{-1}g^n) \notag \\ &=\ (g^{-n+1}x^{-1}g^n)^{-1}g\ =\ g^{-n}xg^n, \end{aligned}\] and \[\begin{aligned} p^{(2n+1)}_g(x)&=p_g(p_g^{(2n)}(x))=p_g(g^{-n}xg^n) \notag \\ &=(g^{-n}xg^n)g=g^{-n}x^{-1}g^{n+1}, \end{aligned}\] as claimed. ◻

Proof. By [lem:pgqg_forms], the cycle containing \(x\) in \(\mathcal F_Q(g)\) has length equal to the least \(\ell\geq1\) for which \(g^{-\ell}x=x\), namely \(\operatorname{ord}(g)\). Hence \(\mathcal F_Q(g)\) is the disjoint union of \(|G|/\operatorname{ord}(g)\) cycles of length \(\operatorname{ord}(g)\). Using [rmk:lucas_forbiddance], \[i(\mathcal F_Q(g))=L_{\operatorname{ord}(g)}^{|G|/\operatorname{ord}(g)}.\] This is the formulation of [ZhaoGroups] needed below. ◻

Proof. Let \(\phi = \frac{1+\sqrt 5}{2}\) be the golden ratio. It is well known that \[\begin{aligned} L_n\ =\ \phi^n + (1-\phi)^n, \end{aligned}\] where notably \(|1-\phi|<1\), so \(L_n \sim \phi^n\). Moreover, since \(1-\phi <0\), one sees that \(L_n > \phi^n \iff n\) is even. Thus, as \(L_4=7\), and \((1-\phi)^n < (1-\phi)^4\) for all \(n>4\), we obtain that \[\begin{aligned} L_n\ \leq\ \left ( 7^{1/4} \right ) ^n \end{aligned}\] for all \(n \geq 4\). This inequality also holds for \(L_1\) and \(L_3\). Thus, as \(a_i \neq 2\) for all \(i\), we have \[\begin{aligned} \prod_{i=1}^jL_{a_i}\ \leq \ \prod_{i=1}^j 7^{a_i/4}\ =\ 7^{N/4}. \end{aligned}\] ◻

Proof. By [lem:FQ_form], \[\begin{aligned} \sum_{g \in G}i(\mathcal F_Q(g))\ &=\ \sum_{g \in G}L_{\operatorname{ord}(g)}^{N/\operatorname{ord}(g)}\ \notag \\ &=\ \, \sum_{\mathclap{\substack{g \in G \\ \operatorname{ord}(g)=2}}} \:L_2^{N/2} + \: \: \sum_{\mathclap{\substack{g \in G \\ \operatorname{ord}(g) \neq 2}}} \: L_{\operatorname{ord}(g)}^{N/\operatorname{ord}(g)} \notag \\ &=\ T \sqrt 3^N + \: \: \sum_{\mathclap{\substack{g \in G \\ \operatorname{ord}(g) \neq 2}}}\: L_{\operatorname{ord}(g)}^{N/\operatorname{ord}(g)}. \end{aligned}\] By [lem:lucas_asym], every term in the summation above is \(O(7^{N/4})\). Thus, \[\begin{aligned} \sum _{g \in G}i(\mathcal F_Q(g))\ =\ T\cdot \sqrt 3^N + (N-T)\cdot O(7^{N/4}), \end{aligned}\] as claimed. ◻

Proof. Suppose \(g \in Z(G)\). By [eq:pg_even_form], \(p_g^{(2)}(x) = g^{-1}xg\). Thus, as \(gx=xg\), we know every \(x\in G\) is contained in either a \(1\)-cycle or a \(2\)-cycle in \(\mathcal F_P(g)\) by the proof of [lem:disjoint_cycles]. In particular, \(x\) is contained in a \(2\)-cycle if and only if \(p_g^{(1)}(x)\neq x\), which is equivalent to \(x^2=g\). Let \[\begin{aligned} r(g)\ :=\ \# \{x \in G: x^2=g\}. \end{aligned}\] Then, the forbiddance graph \(\mathcal F_P(g)\) is composed of \(r(g)\) \(1\)-cycles, and \(\left ( \frac{N-r(g)}{2} \right )\) \(2\)-cycles. Therefore, for any \(g \in Z(G)\), \[\begin{aligned} i(\mathcal F_P(g))\ =\ L_1^{r(g)}\cdot L_2^{\frac{N-r(g)}{2}}\ =\ \sqrt 3^{N-r(g)}. \end{aligned}\] On the other hand, for \(g \not \in Z(G)\), the number of \(2\)-cycles in \(\mathcal F_P(g)\) is bounded above by the number of elements which commute with \(g\), i.e. \(|Z(g)|\). Thus, \[\begin{aligned} i(\mathcal F_P(g)) \ \leq\ \sqrt 3^{|Z(g)|}\cdot O\left ( 7^{(N-|Z(g)|)/4} \right ) \end{aligned}\] from [lem:lucas_asym]. Since \(7^{n/4}\ll\sqrt 3^n\), the RHS is maximized when \(|Z(g)|\) is maximized. By the assumption that \(g \not \in Z(G)\), we know \(Z(g)\) is a proper subgroup, hence \(|Z(g)| \leq N/2\). Therefore, \[\begin{aligned} i(\mathcal F_P(g))\ \leq\ \sqrt 3^{N/2}\cdot O(7^{N/8}) \ =\ O(1.68^N). \end{aligned}\] We therefore get \[\begin{aligned} \sum_{g \in G}i(\mathcal F_P(g))\ &= \sum_{g \in Z(G)}\sqrt 3^{N-r(g)} + \sum_{g \not \in Z(G)}O(1.68^N). \label{eq:FP_true_sum} \end{aligned}\] since \(\sqrt 3^{N-r(g)}\leq \sqrt 3^N\), we have \[\begin{aligned} \sum_{g \in G}i(\mathcal F_P(g))\ \leq\ Z\cdot \sqrt 3^N + (N-Z)\cdot O(1.68^N), \end{aligned}\] which is the second inequality in [eq:FP_asym]. To obtain the lower bound, observe that \(f(x):=\sqrt 3^{N-x}\) is a convex function. Therefore, by Jensen’s inequality, \[\begin{aligned} \frac{1}{Z}\sum_{g \in Z(G)}\sqrt 3^{N-r(g)}\ \geq\ \sqrt 3^{ N-\frac 1Z\sum_{g \in Z(G)}r(g)}\ =\ \sqrt 3^{N-R/Z}. \end{aligned}\] Thus, by [eq:FP_true_sum], \[\begin{aligned} \sum_{g \in G}i(\mathcal F_P(g))\ \geq\ Z\cdot \sqrt 3^{N-R/Z} + (N-Z) \cdot O(1.68^N) \end{aligned}\] as claimed. ◻

Proof. We proceed similarly to the first moment. Let \(p(A) := |AA|\) and \(q(A):= |AA^{-1}|\). Then, \[\begin{aligned} M_2(G)\ :=&\ \sum_{A \subseteq G}(p(A) - q(A))^2\ =\ \sum_{A \subseteq G}\left [ p(A)^2+q(A)^2 - 2p(A)q(A) \right ] . \label{eq:binomvar} \end{aligned}\] note that \[\begin{aligned} p(A)^2\ =&\ \ \left ( \sum_{x}\mathbb 1_{AA}(x) \right ) ^2 = \sum_{g,h}\mathbb 1_{AA}(g)\mathbb 1_{AA}(h), \\ q(A)^2\ =&\ \ \left ( \sum_{x}\mathbb 1_{AA^{-1}}(x) \right ) ^2\ =\ \sum_{g,h}\mathbb 1_{AA^{-1}}(g)\mathbb 1_{AA^{-1}}(h), \\ p(A)q(A)\ =&\ \ \left ( \sum_{g}\mathbb 1_{AA}(g) \right ) \left ( \sum_{h}\mathbb 1_{AA^{-1}}(h) \right ) \ =\ \sum_{g,h}\mathbb 1_{AA}(g) \mathbb 1_{AA^{-1}}(h). \end{aligned}\] Thus, we rewrite [eq:binomvar] as \[\begin{aligned} &\ \ \sum_{A \subseteq G} \sum_{g,h}\left [ \mathbb 1_{AA}(g)\mathbb 1_{AA}(h) + \mathbb 1_{AA^{-1}}(g)\mathbb 1_{AA^{-1}}(h) - 2\cdot \mathbb 1_{AA}(g) \mathbb 1_{AA^{-1}}(h) \right ] \notag \\ =&\ \ \sum_{g,h}\sum_{A \subseteq G}\left [ \mathbb 1_{AA}(g)\mathbb 1_{AA}(h) + \mathbb 1_{AA^{-1}}(g)\mathbb 1_{AA^{-1}}(h) - 2\cdot \mathbb 1_{AA}(g) \mathbb 1_{AA^{-1}}(h) \right ] \notag \\ =&\ \ \sum_{g,h}\left [ \# \{ A: g,h \in AA\} + \#\{A: g, h \in AA^{-1}\} -2 \# \{ A: g \in AA, h \in AA^{-1}\} \right ] . \label{eq:varandsets} \end{aligned}\]

to obtain the expressions in [rmk:two_elm_indep], we use the inclusion-exclusion principle: \[\begin{aligned} \# \{ A: g,h \in AA\}\ =&\ \ 2^{|G|}-\# \{ A: g\not \in AA \text{ or } h \not \in AA\} \notag \\ =&\ \ 2^{|G|}-\#\{A: g \not \in AA\} - \#\{A: h \not \in AA\} \notag \\ &+\ \#\{ A: g \not \in AA \text{ and } h \not \in AA\} \notag \\ =&\ \ 2^{|G|}-i(\mathcal F_{P}(g)) - i(\mathcal F_{P}(h)) + i(\mathcal F_{PP}(g,h)), \label{eq:varprod} \end{aligned}\] and similarly \[\begin{aligned} \# \{ A:g,h\in AA^{-1}\}\ =&\ \ 2^{|G|}-i(\mathcal F_Q(g)) - i(\mathcal F_Q(h)) + i(\mathcal F_{QQ}(g,h)), \label{eq:varquot} \\ \# \{A: g \in AA,h \in AA^{-1}\}\ =&\ \ 2^{|G|} - i(\mathcal F_P(g)) - i(\mathcal F_Q(h)) + i(\mathcal F_{PQ}(g,h)). \label{eq:varboth} \end{aligned}\] Plugging these into [eq:varandsets] yields (after rearranging and canceling) \[\begin{aligned} M_2(G)\ =\ &\sum_{g,h}\left [ i(\mathcal F_P(g))- i(\mathcal F_P(h))+ i(\mathcal F_Q(h))-i(\mathcal F_Q(g)) \right ] \label{eq:varsingles} \\ &+ \sum_{g,h}\left [ i(\mathcal F_{PP}(g,h))+ i(\mathcal F_{QQ}(g,h))- 2 i(\mathcal F_{PQ}(g,h)) \right ] \label{eq:vardoubles} \end{aligned}\] Notice that the entire sum in [eq:varsingles] cancels, and so we are left with \[\begin{aligned} M_2(G)\ =\ \sum_{g,h}\left [ i(\mathcal F_{PP}(g,h))+ i(\mathcal F_{QQ}(g,h))- 2 i(\mathcal F_{PQ}(g,h)) \right ] \end{aligned}\] as claimed. ◻

Proof. When \(g \neq h\), note that \[\begin{aligned} p_g(x)\ &=\ x^{-1}g\ \neq\ x^{-1}h\ =\ p_h(x) , \\q_g(x)\ &=\ g^{-1}x\ \neq \ h^{-1}x\ = \ q_h(x) \end{aligned}\] so every vertex in \(\mathcal F_{PP}(g,h)\) and \(\mathcal F_{QQ}(g,h)\) connects to at least two distinct vertices, possibly including itself. Since a self-adjacent vertex cannot be included in any independent set, we can remove all self-adjacent vertices from \(\mathcal F_{PP}(g,h)\) and \(\mathcal F_{QQ}(g,h)\). Let \(\overline{\mathcal F}_{PP}(g,h)\) be the simple, undirected graph corresponding to \(\mathcal F_{PP}(g,h)\) with all self-adjacent vertices removed, and define \(\overline{\mathcal F}_{QQ}(g,h)\) similarly. It follows that \[\begin{aligned} i(\mathcal F_{PP}(g,h))\ =\ i(\overline{\mathcal F}_{PP}(g,h)), \\ i(\mathcal F_{QQ}(g,h))\ =\ i(\overline{\mathcal F}_{QQ}(g,h)). \end{aligned}\] Moreover, both \(\overline{\mathcal F}_{PP}(g,h)\) and \(\overline{\mathcal F}_{QQ}(g,h)\) have the property that the degree \(d_x\) of each vertex \(x\) is restricted to either \(2,3\), or \(4\), since there must be between \(2\) to \(4\) elements \(y \in G\) with \[\begin{aligned} xy = g, \text{ or } xy=h, \text{ or } yx=g, \text{ or } yx=h, \end{aligned}\] and similar for the quotient. We use the following result to obtain an upper bound on the number of independent sets of these graphs.

Finally, [eq:FPP_bound] and [eq:FQQ_bound] follow from [cor:Zhao_strong_indep] applied to \(\overline{\mathcal F}_{PP}(g,h)\) and \(\overline{\mathcal F}_{QQ}(g,h)\). ◻

Proof. Let \(N_k := |G_k|\). To prove that sufficiently large \(G_k\) are product or quotient-dominant, it suffices to verify the inequality \[\begin{aligned} \frac{1}{2}<\frac{(M_1(G_k))^2}{(2^{N_k}-B(G_k))\cdot (M_2(G_k))} \end{aligned}\] from [prop:dom_ineq].

To prove statement (i) of the theorem, suppose \(Z_k = o(T_k)\). Recall from [cor:FQ_asym] that \[\begin{aligned} Q_k\ =\ T_k \cdot \sqrt 3^{N_k} + (N_k-T_k) \cdot O(7^{{N_k}/4})\ =\ T_k\cdot \sqrt 3^{N_k} + (N_k-T_k) \cdot O(1.68^{N_k}), \end{aligned}\] where the second equality follows from \(7^{1/4}<1.68\). Moreover, from [lem:FP_asym] we have \[\begin{aligned} P_k\ \leq \ Z_k \cdot \sqrt 3^{N_k} + (N_k-Z_k)\cdot O(1.68^{N_k}). \end{aligned}\] we informally write (for the purposes of plugging this into [eq:prod_final_ineq]) \[\begin{aligned} \lim_{k \to \infty}M_1(G_k)\ =& \ \ \lim_{k \to \infty}Q_k - P_k \notag \\ \geq& \ \ \lim _{k \to \infty}\left ( (T_k-Z_k)\sqrt 3^{N_k}+ (Z_k-T_k)\cdot O(1.68^{N_k}) \right ) \notag \\ =& \ \ \lim_{k \to \infty} T_k\sqrt 3^{N_k} \left ( \left ( 1-\frac{Z_k}{T_k} \right ) + \left ( \frac{Z_k}{T_k}-1 \right ) \frac{O(1.68^{N_k})}{\sqrt 3^{N_k}} \right ) \notag \\ =& \ \ \lim_{k \to \infty} T_k\sqrt 3^{N_k} \label{eq:M1_mptq_lim} \end{aligned}\] by the assumption that \(Z_k = o(T_k)\), and the fact that \(1.68 < \sqrt 3\). This also establishes that \(M_1>0\), so we may proceed with case (i) of [prop:dom_ineq]. Similarly, \[\begin{aligned} \lim_{ k \to \infty}\left ( 2^{N_k}-B_k \right ) \ \leq&\ \ \lim_{k \to \infty}Q_k + P_k \notag \\ \leq& \ \ \lim_{k \to \infty}\left ( (T_k+Z_k)\sqrt 3^{N_k} + (2N_k-T_k-Z_k)\cdot O(1.68^{N_k}) \right ) \notag \\ =& \ \ \lim_{k \to \infty}T_k\sqrt 3^{N_k}\left ( \left ( 1 + \frac{Z_k}{T_k} \right ) + \left ( 2\frac{N_k}{T_k}-1-\frac{Z_k}{T_k} \right ) \frac{O(1.68^{N_k})}{\sqrt 3^{N_k}} \right ) \notag \\ =&\ \ \lim_{k \to \infty}T_k \sqrt 3^{N_k}. \end{aligned}\] Finally, \[\begin{aligned} \lim_{k \to \infty} M_2(G_k)\ =&\ \ \lim_{k \to \infty}\left ( Q_k + P_k + QQ_k + PP_k \right ) \notag \\ =&\ \ \lim _{k \to \infty}T_k\sqrt 3^{N_k} + QQ_k + PP_k \notag \\ \leq &\ \ \lim _{k \to \infty} T_k\sqrt 3^{N_k}+2N_k^2\cdot19^{N_k/6} \notag \\ =&\ \ \lim_{k \to \infty}T_k\sqrt 3^{N_k}\left ( 1+\frac{2N_k^2\cdot 19^{N_k/6}}{T_k\sqrt 3^{N_k}} \right ) \notag \\ =&\ \ \lim_{k \to \infty}T_k \sqrt 3^{N_k}, \end{aligned}\] since \(19^{1/6}<\sqrt 3\). We thus conclude that \[\begin{aligned} \label{eq:prod_final_ineq} \lim _{k \to \infty}\frac{(M_1(G_k))^2}{(2^{N_k}-B_k)\cdot M_2(G_k)}\ \geq\ \lim_{k \to \infty} \frac{\left ( T_k\sqrt 3^{N_k} \right ) ^2}{T_k\sqrt 3^{N_k}\cdot T_k\sqrt 3^{N_k}}=1>1/2, \end{aligned}\] hence by [prop:dom_ineq], \(G_k\) is product-dominant for sufficiently large \(k\).

for case (ii) of the theorem, suppose \(T_k\cdot \sqrt 3^{R_k/Z_k} = o(Z_k)\). By [lem:FP_asym], \[\begin{aligned} P_k\ \geq \ Z_k \cdot \sqrt 3^{N_k-R_k/Z_k} + (N_k-Z_k)\cdot O(1.68^{N_k}). \end{aligned}\] Since every element \(g \in Z_k\) has \(g^2 \in Z_k\), we have \(R_k\geq Z_k\), and therefore \(T_k = o(Z_k)\) as well.

Thus, \[\begin{aligned} \lim_{k \to \infty}M_1(G_k)\ &=\ \lim_{k \to \infty}Q_k-P_k \notag \\ &\leq\ \lim_{k \to \infty} T_k\cdot \sqrt 3^{N_k}-Z_k\cdot \sqrt 3^{N_k-R_k/Z_k}+(Z_k-T_k)\cdot O(1.68^{N_k}) \notag \\ &=\ \lim_{k \to \infty} Z_k\sqrt 3^{N_k-R_k/Z_k}\left ( \frac{T_k\cdot \sqrt 3^{R_k/Z_k}}{Z_k}-1+\left ( 1-\frac{T_k}{Z_k} \right ) \cdot\frac{O(1.68^{N_k})}{\sqrt 3^{N_k-R_k/Z_k}} \right ) \notag \\ &=\ \lim_{k \to \infty} Z_k \sqrt 3^{N_k - R_k/Z_k}\left ( -1 + \frac{O(1.68^{N_k}) \cdot \sqrt 3^{R_k/Z_k}}{\sqrt 3^{N_k}} \right ) . \end{aligned}\] By the assumption that \(T_k \cdot \sqrt 3^{R_k/Z_k}=o(Z_k)\), we know that for \(k\) sufficiently large, \[\begin{aligned} 0 \leq T_k < Z_k\leq N_k, \end{aligned}\] If \(T_k\geq 1\), it follows that \[\begin{aligned} \sqrt 3^{R_k/Z_k}\leq N_k. \end{aligned}\] On the other hand, if \(T_k=0\), then \(G_k\) has no order-\(2\) elements, and therefore must have odd order. If \(x^2 \in Z(G_k)\), then \(\overline x^2 = \overline e\) in the quotient group \(G_k / Z(G_k)\), but this quotient group has odd order as well, so it must be that \(\overline x = \overline e\), hence \(x \in Z(G_k)\). Thus, \(R_k/Z_k=1\), so \[\begin{aligned} \sqrt 3^{R_k/Z_k}=\sqrt 3. \end{aligned}\] In any case, we may assume \(\sqrt 3^{R_k/Z_k}\leq N_k\) for \(k\) sufficiently large, and then \[\begin{aligned} \lim_{k \to \infty}\frac{O(1.68^{N_k}) \cdot \sqrt 3^{R_k/Z_k}}{\sqrt 3^{N_k}} \leq \lim_{ k \to \infty}\frac{O(1.68^{N_k}) \cdot N_k}{\sqrt 3^{N_k}}\ =\ 0. \end{aligned}\] Therefore, \[\begin{aligned} \lim_{k \to \infty}M_1(G_k)\ =-\lim_{k \to \infty}Z_k \sqrt 3^{N_k-R_k/Z_k}. \end{aligned}\] Hence, for \(k\) sufficiently large, \(M_1(G_k)<0\), and we may proceed with case (ii) of [prop:dom_ineq]. The analysis above showed that \(P_k\) dominates over \(Q_k\), and its terms of the form \(\sqrt 3^x\) dominate \(QQ_k\) and \(PP_k\) as well by [lem:double_bound]. Hence, one sees that, similar to the first case, \[\begin{aligned} \lim_{k \to \infty}\frac{(Q_k-P_k)^2}{(Q_k+P_k)(Q_k+P_k+QQ_k+PP_k)}\ = \ 1\ >\ 1/2, \end{aligned}\] thus \(G_k\) is quotient-dominant for sufficiently large \(k\). ◻

Proof. Let \(D_k\) be the dihedral group on \(k\) vertices. We have \[\begin{aligned} Z_k\ =\ \begin{cases}2 & k \text{ even}, \\ 1 & k \text{ odd},\end{cases} \end{aligned}\] and \[\begin{aligned} T_k\ =\ \begin{cases}k+1 & k \text{ even,} \\ k & k\text{ odd.}\end{cases} \end{aligned}\] Let \(Q_k,P_k,QQ_k,PP_k\) be as in [lem:PQPPQQ]. By [cor:FQ_asym], \(Q_k \geq T_k \cdot \sqrt 3^{N_k}\). By [lem:FP_asym], \[\begin{aligned} P_k\ \leq\ Z_k \cdot \sqrt 3^{N_k} + (N_k-Z_k)\cdot 1.68^{N_k}. \end{aligned}\] Note that the Big-O notation around \(1.68^{N_k}\) could be dropped by the proof of [lem:lucas_asym] and [lem:FP_asym]. Furthermore, by [lem:double_bound], \[\begin{aligned} QQ_k &\leq \frac{N_k(N_k-1)}{2} \cdot 19^{N_k/6}, \\ PP_k &\leq \frac{N_k(N_k-1)}{2} \cdot 19^{N_k/6}. \end{aligned}\] By [prop:dom_ineq] and [lem:PQPPQQ], it suffices to find \(M\) such that \(k \geq M\) implies \[\begin{aligned} \frac{\left [ (T_k - Z_k ) \sqrt 3^{N_k}-(N_k-Z_k) 1.68^{N_k} \right ] ^2}{\left [ (T_k + Z_k ) \sqrt 3^{N_k}+(N_k-Z_k) 1.68^{N_k} \right ] \left [ (T_k + Z_k ) \sqrt 3^{N_k}+(N_k-Z_k) 1.68^{N_k}+N_k(N_k-1) 19^{N_k/6} \right ] } \\ > 1/2. \end{aligned}\] Recall that \(N_k=2k\). When \(k\) is even, the expression above evaluates to \[\begin{aligned} \frac{\left [ (k-1)3^k-(2k-2)1.68^{2k} \right ] ^2}{\left [ (k+3)3^k+(2k-2)1.68^{2k} \right ] \left [ (k+3)3^k+(2k-2)1.68^{2k} + 2k(2k-1)19^{k/3} \right ] }. \end{aligned}\] One can check that this expression is strictly larger than \(1/2\) for all \(k \geq 56\). When \(k\) is odd, the expression evaluates to \[\begin{aligned} \frac{\left [ (k-1)3^k-(2k-1)1.68^{2k} \right ] ^2}{\left [ (k+1)3^k+(2k-1)1.68^{2k} \right ] \left [ (k+1)3^k+(2k-1)1.68^{2k} + 2k(2k-1)19^{k/3} \right ] }. \end{aligned}\] One can check that this expression is strictly larger than \(1/2\) for all \(k \geq 55\). Thus, \(D_k\) is product-dominant for all \(k\geq 55\). Computational algorithms (TODO) make computation of \(M_1(G)\) and \(M_2(G)\) fast, and in particular it’s possible to compute them for \(D_k\) with \(k \leq 54\). However, computing the actual value for \(2^{|G|}-B\) is slow, but computing the bound \(Q_k +P_k\) is fast. Thus, via explicit computation, we determine further that \(D_k\) is product dominant for \(31 \leq k \leq 54\). The rest of the dihedral groups (\(k \leq 30\)) must be evaluated manually (TODO). ◻

Proof. For symmetric groups \(\{S_k\}\) with \(k\geq3\), we have \(Z_k=1\) and \(T_k \geq \binom{k}{2}\), so \(Z_k = o(T_k)\), and Case (i) of [thm:mptqresult] applies. ◻

Proof. Let \(G\) be a non-abelian finite simple group. Then, \(Z=1\) since the center is a normal subgroup. Moreover, by the Feit-Thompson theorem [feit-thompson], \(G\) has even order, hence has an element \(g\) of order \(2\). Let \(\mathcal C_g\) be the conjugacy class of \(g\). Then, the action of \(G\) on \(\mathcal C_g\) by conjugation induces a homomorphism \(\varphi :G \to S(\mathcal C_g)\). If \(\ker \varphi = G\), then \(xgx^{-1}=g\) for all \(x \in G\), hence \(g \in Z(G)\) which cannot be the case. Therefore, \(\ker\varphi\) is a proper normal subgroup of \(G\), thus is trivial. So, \(G\) embeds in \(S(\mathcal C_g)\), and \(|G| \leq |\mathcal C_g|!\). Therefore, if \(\{G_k\}\) is a family of finite simple groups with \(|G_k| \to \infty\), we must have an involution \(g_k \in G_k\) for all \(k\), and since \(|G_k| \leq |\mathcal C_{g_k}|!\), we must have \(|\mathcal C_{g_k}| \to \infty\). Finally, every element in the conjugacy class \(\mathcal C_{g_k}\) must also have order \(2\), thus \(T_k \geq |\mathcal C_{g_k}| \to \infty\), so it follows that \(Z_k = 1 = o(T_k)\), and Case (i) of [thm:mptqresult] applies. ◻

Proof. Let \(\{G_k\}\) be a sequence of groups of odd order. Then, \(T_k=0\) and \(Z_k \geq 1\), so we immediately have \[\begin{aligned} T_k \cdot \sqrt 3^{R_k/Z_k}\ =\ 0\ =\ o(Z_k), \end{aligned}\] and Case (ii) [thm:mptqresult] applies. ◻

Proof. Let \(T\) be the number of elements of order \(2\). Then the first isomorphism theorem on the map \(x\mapsto 2x\) gives \(|G| = m\cdot (T+1)\).

Let \(P\) and \(Q\) be as in [lem:PQPPQQ] (we’re removing the underscore \(k\) notation as it’s less necessary here). Then, \[\begin{aligned} P \ &=\ (N-m)\sqrt{3}^N + m\sqrt{3}^{N-(T+1)} \notag \\ &=\ mT\sqrt{3}^N + m\sqrt{3}^{N-(T+1)} \label{eq:abelianP} \\ Q \ &\leq\ T\sqrt{3}^N + (N-T)7^{N/4}. \label{eq:abelianQ} \end{aligned}\] Let \(Q^+ := T\sqrt{3}^N + (N-T)7^{N/4}\), so \(Q \leq Q^+\). If \(m\geq 6\), then numerical calculations on [eq:abelianP] and [eq:abelianQ] shows that for any \(T \geq 1\), \[\begin{aligned} M_1(G)\ \overset{\eqref{eq:M1_sum}}{=}\ Q - P \ \leq\ Q^+-P \ <\ 0, \end{aligned}\] so we’ll be able to apply (ii) from [prop:dom_ineq]. Recall from [lem:PQPPQQ] and [lem:double_bound], (with \(PP\) and \(QQ\) as in [lem:PQPPQQ], not to be confused with multiplying \(P\cdot P\) and \(Q\cdot Q\)), \[\begin{aligned} \frac{M_1^2}{(2^N-B)M_2} \ &\geq\ \frac{(Q-P)^2}{(P+Q)\cdot(Q+P + QQ+PP)} \notag \\ &\ge \frac{(Q-P)^2}{(P+Q)\cdot(Q+P+N(N-1)19^{N/6})} \notag \\ &\ge \frac{(P-Q^+)^2}{(P+Q^+)(P+Q^++N(N-1)19^{N/6})}. \end{aligned}\] Let \[\begin{aligned} u\ :=\ \frac{Q^+}{P}\quad\mbox{and}\quad v\ :=\ \frac{N(N-1)19^{N/6}}{P}, \end{aligned}\] so we have \[\begin{aligned} \frac{M_1^2}{(2^N-B)M_2} \ \geq\ \frac{(1-u)^2}{(1+u)(1+u+v)}. \end{aligned}\] By [prop:dom_ineq], it suffices to prove \[\begin{aligned} \frac{(1-u)^2}{(1+u)(1+u+v)} \ >\ \frac{1}{2} \end{aligned}\] which is equivalent to proving that \[\begin{aligned} f(u,v) \ :=\ u^2-6u+1 - v(1+u)\ >\ 0. \end{aligned}\] First, observe \(\partial f/\partial u = -4<0\) and \(\partial f/\partial v = -(1+u)<0\), so \(f\) is strictly decreasing in each of \(u\) and \(v\). We find an explicit upper bound for \(u\) and \(v\), which only depends on \(N\). We have \[\begin{aligned} u \ &=\ \frac{T\sqrt{3}^N+(N-T)7^{N/4}}{(N-m)\sqrt{3}^N + m\sqrt{3}^{N-(T+1)}} \notag \\ &\leq\ \frac{T\sqrt{3}^N+(N-T)7^{N/4}}{mT\sqrt{3}^N} \notag \\ &=\ \frac{1}{m} + \frac{N-T}{mT} (7/9)^{N/4} \notag \\ &\leq\ \frac{1}{6} + 2\left(\frac{7}{9}\right)^{N/4} \end{aligned}\] as \((N-T)/mT < N/mT = (T+1)/T \leq 2\). Moreover, \[\begin{aligned} v\ &=\ \frac{N(N-1)19^{N/6}}{(N-m)\sqrt{3}^N+m\sqrt{3}^{N-(T+1)}} \notag \\ &\leq\ \frac{N(N-1)19^{N/6}}{mT\sqrt{3}^N} \notag \\ &\leq\ 2(N-1)\left(\frac{19}{27}\right)^{N/6}, \end{aligned}\] since \(N/mT<2\). Thus, \[\begin{aligned} f(u,v)\ &\geq\ f\left(\frac{1}{6}+2\left(\frac{7}{9}\right)^{N/4}, 2(N-1)\left(\frac{19}{27}\right)^{N/6}\right) \ =:\ h(N). \end{aligned}\] Finally, it is not hard to show that \(h(N)\) is increasing for every \(N\geq 12\), and numerical analysis shows that \(h(N) > 0\) for all \(N\geq 163\), as claimed. ◻

Proof. Let \[\begin{aligned} S\ :=\ \left \{ p_g^{(n)}(x) : n \in \mathbb{Z}^+ \right \} \end{aligned}\] be the elements in the cycle containing \(x\) in \(\mathcal F_P(g)\). The action of repeatedly applying \(p_g\) induces a cyclic group structure on \(S\), where \(x\) has order \(\ell_{g,x}\) by minimality. By Lagrange’s theorem, if \(p_g^{(d)}(x)=x\), then \(\ell_{g,x} \mid d\). ◻

Proof. By [lem:pgqg_forms], \[\begin{aligned} p^{2\operatorname{ord}(g)}_g(x)=g^{-\operatorname{ord}(g)}xg^{\operatorname{ord}(g)}=x, \end{aligned}\] so by [lem:divisibility] we have \(\ell_{g,x} \mid 2\operatorname{ord}(g)\). ◻

Proof. Recall that \(p_g^{(2k)}(x) = x \iff xg^k=g^kx\). Thus, \(L(d,g) = C_G(g^k)\). The second equality in [eq:L_even_d] follows from the orthogonality relations of characters.

When \(d=2k+1\) is odd, then by [lem:pgqg_forms] \[\begin{aligned} p_g^{(2k+1)}(x) =x \iff g^{-k}x^{-1}g^{k+1}=x. \end{aligned}\] Substituting \(x=g^{k+1}y\) yields \[\begin{aligned} p_g^{(d)}(x)=x\ &\iff\ g^{-k}y^{-1}g^{-(k+1)}g^{k+1}=g^{k+1}y \\ &\iff\ g^{-d}=y^2. \end{aligned}\] Our substitution induces a bijection on \(G\), hence the number of \(y \in G\) satisfying \(g^{-d}=y^2\) is precisely \(L(d,g)\). The number of square roots of \(g^{-d}\) is known in general to be \[\begin{aligned} \sum_{i=1}^n\nu(\chi_i) \cdot \chi_i(g^{-d}) \end{aligned}\] (see [isaacs2006character] or [rowe2022squareroots], for example). This proves [eq:L_odd_d]. ◻

Proof. Define \[\begin{aligned} f(d) \ :=\ \#\{x\in G:\ell_{g,x}=d\}. \end{aligned}\] Then, by [lem:divisibility] we have \[\begin{aligned} L(m,g)\ =\ \sum_{d\mid m}f(d). \end{aligned}\] Thus, by the Möbius inversion formula, we have \[\begin{aligned} f(m)=\sum_{d\mid m}\mu(m/d)\cdot L(d,g) \end{aligned}\] where \(\mu\) is the Möbius function. This gives the number of \(x\in G\) contained in \(m\)-cycles in \(\mathcal F_P(g)\). We divide by \(m\) to obtain the total number of \(m\)-length cycles. ◻

Proof. By [lem:M1_sum], \[\begin{aligned} M_1(G)\ =\ \sum_{g \in G}i(\mathcal F_Q(g)) - i(\mathcal F_P(g)). \label{eq:M1_mention2} \end{aligned}\] By the work done in 3 (namely [lem:disjoint_cycles], [rmk:lucas_forbiddance], and [lem:FQ_form]), as well as the definition of \(c(m,g)\), and [lem:divisibility], we have \[\begin{aligned} i(\mathcal F_Q(g)) - i(\mathcal F_P(g))\ = \ L_{\operatorname{ord}(g)}^{|G|/\operatorname{ord}(g)}-\prod_{m \mid (2 \cdot \operatorname{ord}g)}L_m^{c(m,g)} .\label{eq:idiffinlucas} \end{aligned}\] Moreover, from the proof of [lem:M1_sum], recall that \[\begin{aligned} i(\mathcal F_Q(g)) - i(\mathcal F_P(g)) \ = \ \#\{A \subseteq G: g\in AA\} - \# \{ A \subseteq G: g \in AA^{-1}\}. \label{eq:subsetcontainment} \end{aligned}\] for any \(g \in G\), \(A \subseteq G\), and any \(G\)-automorphism \(\sigma\), note that \[\begin{aligned} g \in AA \ &\iff\ g = xy \text{ for } x,y\in A \\ &\iff\ \sigma(g)=\sigma(x)\sigma(y) \text{ for } x,y \in A \\ &\iff\ \sigma(g) \in \sigma(A)\sigma(A). \end{aligned}\] We obtain a similar equivalence for \(g \in AA^{-1}\). Therefore the expressions in [eq:subsetcontainment] are invariant under any \(G\)-automorphism applied to \(g\). In particular, they are invariant under the action of conjugation, so it follows from [eq:idiffinlucas] that \[\begin{aligned} \sum_{g \in G}i(\mathcal F_Q(g)) - i(\mathcal F_P(g))\ &=\ \sum _{i=1}^n|\mathcal C_i|\left ( i(\mathcal F_Q(g_i)) - i(\mathcal F_P(g_i)) \right ) \notag \\ &=\ \sum_{i=1}^n|\mathcal C_i|\left ( L_{\operatorname{ord}{g_i}}^{|G|/\operatorname{ord}{g_i}} - \prod_{m \mid \left ( 2\cdot \operatorname{ord}{g_i} \right ) }L_m^{c(m,g_i)} \right ) . \end{aligned}\] ◻