\documentclass{conjura-conjecture}

\runninghead{GENERALIZED MIRROR THEORY}

\begin{document}

\cjkicker{CONJURA \textperiodcentered{} OPEN PROBLEM}
\cjtitle{The Open Generalized Mirror Theory Conjecture}
\cjsubtitle{Exact Multi-Graph Bounds Beyond the $O(2^{n/4})$ Regime}
\cjstatus{Statement: AI-written, not yet formalized.}
\cjcategory{Symmetric-Key Cryptography.}

\vspace{0.4em}

Mirror Theory, initially introduced by \href{https://iacr.org/archive/crypto2003/27290510/27290510.pdf}{Patarin (2003)}, provides lower bounds on the number of non-degenerate solutions to systems of bivariate linear equations over $\mathbb{F}_2^n$. While recent breakthroughs (e.g., \href{https://eprint.iacr.org/2022/686}{Cogliati et al., 2023}) have rigorously established the theory for component sizes up to $\xi_{\max} = O(2^{n/4}/\sqrt{n})$, the fully generalized conjecture for arbitrary dependency graphs up to the information-theoretic limit remains an open problem in theoretical cryptography. This document provides a self-contained statement of the open Generalized Mirror Theory Conjecture.

\section{Formal Preliminaries}

Let $V = \{p_1, p_2, \dots, p_q\}$ be a set of variables taking values in $\{0,1\}^n$, where $N = 2^n$. We consider systems of bivariate affine equations over $\mathbb{F}_2^n$ defined on a multi-graph $G = (V, E)$.

\begin{definition}[Affine Equation System]
Let $G = (V, E)$ be a connected graph with $q = |V|$ vertices and $m = |E|$ edges. Let $\lambda : E \to \{0,1\}^n \setminus \{0^n\}$ be an edge-labeling function assigning non-zero target constants to each edge. The system of equations is given by:
\begin{equation}
\mathcal{E}(G, \lambda) := \Bigl\{ p_i \oplus p_j = \lambda_{i,j} \;\Big|\; e = (p_i, p_j) \in E \Bigr\}.
\end{equation}
\end{definition}

\begin{definition}[Non-Degenerate Solutions]
A tuple $(P_1, \dots, P_q) \in (\{0,1\}^n)^q$ is called a \textbf{valid (non-degenerate) solution} to $\mathcal{E}(G, \lambda)$ if:
\begin{enumerate}[label=\roman*.]
    \item $P_i \oplus P_j = \lambda_{i,j}$ for all $(p_i, p_j) \in E$.
    \item $P_i \neq P_j$ for all $i \neq j$ (all variables in $V$ are pairwise distinct).
\end{enumerate}
We denote the set of all non-degenerate solutions by $\mathbf{Sol}(\mathcal{E}(G, \lambda))$ and its cardinality by $h(G, \lambda) := |\mathbf{Sol}(\mathcal{E}(G, \lambda))|$.
\end{definition}

\begin{definition}[Cycle Consistency and Component Size]
A system $\mathcal{E}(G, \lambda)$ is \textbf{cycle-consistent} if for every cycle $C$ in $G$, the XOR sum of labels along the cycle evaluates to $0^n$. Let $\xi_{\max}(G)$ denote the maximum size (number of vertices) of any connected component of $G$, and let $\nu(G) = |E| - |V| + c(G)$ be the circuit rank (cyclomatic number) of $G$, where $c(G)$ is the number of connected components.
\end{definition}

\section{The Unconditional Generalized Mirror Theory Conjecture}

While localized versions of Mirror Theory have been proven for trees and bounded-degree graphs up to $\xi_{\max} = O(N^{1/4})$, the full asymptotic statement for arbitrary graph topologies up to $O(N^{1/2})$ or higher query limits remains open.

\begin{conjecture}[Generalized Mirror Theory Conjecture]
Let $G = (V, E)$ be a graph with $q = |V|$ vertices and $m = |E|$ edges. Let $\mathcal{E}(G, \lambda)$ be a cycle-consistent affine system. Assume that $q \le o(N^{1/2})$ and that the maximum component size satisfies $\xi_{\max}(G) \le o(N^{1/2})$.

Then, the number of non-degenerate solutions $h(G, \lambda)$ satisfies the tight lower bound:
\begin{equation}
h(G, \lambda) \ge \frac{(N)_{q}}{N^m} \cdot \left( 1 - O\left( \frac{q \cdot \xi_{\max}(G)}{N} \right) \right),
\end{equation}
where $(N)_q = N(N-1)\dots(N-q+1)$ denotes the falling factorial.

Equivalently, for a collection of $c$ connected tree components $T_1, \dots, T_c$ with $|V(T_k)| = q_k$, $q = \sum q_k$, and $m = q - c$:
\begin{equation}
h(G, \lambda) \ge \frac{N^q}{N^{q-c}} \prod_{i=0}^{q-1} \left(1 - \frac{i}{N}\right) \left( 1 - \epsilon(q, \xi_{\max}, N) \right),
\end{equation}
where $\epsilon(q, \xi_{\max}, N) \to 0$ as long as $q \cdot \xi_{\max}(G) = o(N)$.
\end{conjecture}

\section{State of the Art and Theoretical Gaps}

\begin{table}[h!]
\centering
\small
\begin{tabularx}{\textwidth}{@{}XXXl@{}}
\toprule
\textbf{Reference} & \textbf{Scope / Topology} & \textbf{Max Component ($\xi_{\max}$)} & \textbf{Status} \\ \midrule
\href{https://iacr.org/archive/crypto2003/27290510/27290510.pdf}{Patarin (2003)}, \href{https://doi.org/10.1007/11734727_25}{Patarin (2005)} & Linear Graphs / Trees & $\xi_{\max} = O(1)$ & Gaps identified \\
\href{https://yannickseurin.github.io/assets/papers/CogliatiS18_DCC.pdf}{Cogliati \& Seurin (2018)} & Circle Graphs ($\nu=1$) & $\xi_{\max} = O(N^{1/3})$ & Proven \\
\href{https://eprint.iacr.org/2022/686}{Cogliati et al. (2023)} & Arbitrary Forest Graphs & $\xi_{\max} = O(N^{1/4}/\sqrt{n})$ & Fully Proven \\
\textbf{Open Conjecture} & \textbf{Arbitrary Multi-Graphs} & $\mathbf{\xi_{\max} = o(N^{1/2})}$ & \textbf{OPEN} \\ \bottomrule
\end{tabularx}
\caption{Evolution of Mirror Theory bounds for system size $q$ and component size $\xi_{\max}$.}
\end{table}

\paragraph{Why the Conjecture Remains Open:}
\begin{enumerate}
    \item \textbf{High-Order Link Deletions:} Current algebraic techniques (such as link-deletion equations) rely on induction over component sizes. When $\xi_{\max}$ exceeds $O(N^{1/4})$, higher-order dependency intersections generate non-trivial error terms that cannot be absorbed without explicit structural cancellation lemmas.
    \item \textbf{Multi-Cycle Dependencies:} For graphs with high cyclomatic numbers ($\nu(G) > 1$), handling non-equations ($P_i \neq P_j$) alongside linear constraints requires tracking exact character sums over non-abelian representations, which currently lack tight lower bounds.
\end{enumerate}

\end{document}
