source/tex/src/appendix_theo.tex

\onecolumn

\section*{Appendix}

\section{Theoretical Details and Proofs}
\label{app:info_theory}

\subsection{Information-Theoretic Preliminaries}
\label{app:preliminaries}

\begin{definition}[Mutual Information~\cite{cover1999elements}]
For random variables $X$ and $Y$ with joint distribution $P_{X,Y}$ and marginals $P_X$, $P_Y$, the mutual information is:
\begin{equation}
I(X; Y) = D_{KL}(P_{X,Y} \| P_X \otimes P_Y) = \sum_{x,y} P(x,y) \log \frac{P(x,y)}{P(x)P(y)}
\end{equation}
Mutual information is symmetric, non-negative, and equals zero if and only if $X \perp Y$.
\end{definition}

\begin{definition}[Kullback-Leibler Divergence]
For distributions $P$ and $Q$ over the same space:
\begin{equation}
D_{KL}(P \| Q) = \sum_x P(x) \log \frac{P(x)}{Q(x)}
\end{equation}
$D_{KL}(P \| Q) \geq 0$ with equality if and only if $P = Q$.
\end{definition}

\begin{definition}[Mixture Distribution]
\label{def:mixture}
Given column distributions $\{P_j\}_{j=1}^m$, the mixture distribution is:
\begin{equation}
Q(v) = \frac{1}{m}\sum_{j=1}^m P_j(v)
\end{equation}
This is the marginal distribution of a cell $T_{i,J}$ when $J \sim \text{Uniform}([m])$.
\end{definition}

\begin{definition}[Position-to-Column Mapping]
\label{def:col_mapping}
For positions in the data region of a linearized table ($t > m$), define:
\begin{equation}
\text{col}(t) = ((t - m - 1) \mod m) + 1 \in [m]
\end{equation}
\end{definition}

\subsection{Assumptions}
\label{app:assumptions}

\begin{assumption}[Column Semantic Consistency]
\label{ass:consistency}
All cells in column $j$ are drawn from the same distribution:
\begin{equation}
T_{i,j} \sim P_j, \quad \forall i \in [n], \, \forall j \in [m]
\end{equation}
\end{assumption}

\begin{assumption}[Column Distribution Distinctiveness]
\label{ass:distinct}
Different columns have statistically distinguishable distributions:
\begin{equation}
D_{KL}(P_j \| P_k) > 0, \quad \forall j \neq k
\end{equation}
Equivalently, for each pair $j \neq k$, there exists some value $v$ such that $P_j(v) \neq P_k(v)$.
\end{assumption}

\begin{remark}[On Intra-Column Independence]
\label{rmk:intra_col}
We do \textbf{not} assume $T_{i,j} \perp T_{k,j} \mid j$ (conditional independence within columns). Real tables often exhibit intra-column dependencies (e.g., sorted data, time series). Our proofs analyze the conditional independence case to establish a \textit{lower bound} on $I^{same}$; any intra-column dependency strictly increases the mutual information.
\end{remark}

\subsection{Some Lemmas}
\label{app:same_col}

\begin{lemma}[Same-Column Pair Mutual Information]
\label{lem:same_col}
Let $J \sim \text{Uniform}([m])$. Under Assumptions~\ref{ass:consistency} and~\ref{ass:distinct}:
\begin{enumerate}
    \item[(i)] $I^{same} := I(T_{1,J}; T_{2,J}) > 0$
    \item[(ii)] For any $i \neq k$: $I(T_{i,J}; T_{k,J}) = I^{same}$
\end{enumerate}
That is, the same-column mutual information is strictly positive and independent of row indices.
\end{lemma}

\begin{proof}
We prove both parts simultaneously.

\textbf{Step 1: Marginal distributions.}
For any row index $i$, by Assumption~\ref{ass:consistency} and $J \sim \text{Uniform}([m])$:
\begin{equation}
P(T_{i,J} = a) = \sum_{j=1}^m P(J=j) P_j(a) = \frac{1}{m}\sum_{j=1}^m P_j(a) = Q(a)
\end{equation}
This holds for all $i$, so all $T_{i,J}$ share the same marginal distribution $Q$.

\textbf{Step 2: Joint distribution.}
For any $i \neq k$, conditioning on the column:
\begin{equation}
P(T_{i,J} = a, T_{k,J} = b) = \sum_{j=1}^m P(J=j) \cdot P(T_{i,j} = a, T_{k,j} = b \mid J=j)
\end{equation}

To establish a lower bound independent of intra-column structure, consider the case where $T_{i,j} \perp T_{k,j} \mid j$. Then:
\begin{equation}
P(T_{i,J} = a, T_{k,J} = b) = \frac{1}{m}\sum_{j=1}^m P_j(a) P_j(b) =: R(a,b)
\label{eq:joint_R}
\end{equation}

Note that $R(a,b)$ depends only on the column distributions $\{P_j\}$, not on $i$ or $k$. If $T_{i,j} \not\perp T_{k,j} \mid j$, the actual joint distribution differs from $R$, but we will show $R \neq Q \otimes Q$, which implies $I(T_{i,J}; T_{k,J}) > 0$ in all cases.

\textbf{Step 3: Comparison with product of marginals.}
Under independence, we would have:
\begin{equation}
Q(a) Q(b) = \frac{1}{m^2} \sum_{j=1}^m \sum_{l=1}^m P_j(a) P_l(b)
\end{equation}

Consider the diagonal $a = b$:
\begin{align}
R(a,a) - Q(a)^2 &= \frac{1}{m}\sum_{j=1}^m P_j(a)^2 - \frac{1}{m^2}\left(\sum_{j=1}^m P_j(a)\right)^2 \nonumber \\
&= \frac{1}{m^2}\left[ m\sum_{j=1}^m P_j(a)^2 - \left(\sum_{j=1}^m P_j(a)\right)^2 \right] \nonumber \\
&= \frac{\text{Var}_j[P_j(a)]}{m}
\label{eq:variance_form}
\end{align}
where $\text{Var}_j[P_j(a)] = \frac{1}{m}\sum_j P_j(a)^2 - \left(\frac{1}{m}\sum_j P_j(a)\right)^2$ is the variance of $P_j(a)$ across columns.

\textbf{Step 4: Positivity.}
By Assumption~\ref{ass:distinct}, there exist $j \neq l$ with $P_j \neq P_l$. Hence there exists some $a$ with $P_j(a) \neq P_l(a)$, implying $\text{Var}_j[P_j(a)] > 0$.

Therefore $R(a,a) > Q(a)^2$ for some $a$, so $R \neq Q \otimes Q$.

\textbf{Step 5: Conclusion.}
Since the joint distribution differs from $Q \otimes Q$:
\begin{equation}
I(T_{i,J}; T_{k,J}) = D_{KL}(P_{T_{i,J}, T_{k,J}} \| Q \otimes Q) > 0
\end{equation}

Moreover, under conditional independence, the joint is exactly $R(a,b)$ from~\eqref{eq:joint_R}, which is independent of $i,k$. Thus $I(T_{i,J}; T_{k,J})$ is constant for all $i \neq k$, proving part (ii).
\end{proof}

\begin{lemma}[Periodic Structure]
\label{lem:periodic}
For a table with $n$ rows and $m$ columns, and any $k \in \{1, \ldots, n-1\}$:
\begin{equation}
\bar{I}_{table}(km) = I^{same}
\end{equation}
\end{lemma}

\begin{proof}
\textbf{Step 1: Same-column positions.}
For $t, t' > m$ in the data region:
\begin{equation}
\text{col}(t) = \text{col}(t') \iff t' - t \equiv 0 \pmod{m}
\end{equation}

\textbf{Step 2: Structure at lag $km$.}
When $d = km$ with $1 \leq k \leq n-1$, for each $t \in \mathcal{S}_{km} = \{t : m < t \leq L - km\}$:
\begin{itemize}
    \item $W_t = T_{r_1, c}$ for some row $r_1$ and column $c = \text{col}(t)$
    \item $W_{t+km} = T_{r_1+k, c}$ (same column, row differs by $k$)
\end{itemize}

By Lemma~\ref{lem:same_col}(ii):
\begin{equation}
I(W_t; W_{t+km}) = I(T_{r_1, c}; T_{r_1+k, c}) = I^{same}
\end{equation}

\textbf{Step 3: Averaging.}
Since every pair contributes equally:
\begin{equation}
\bar{I}_{table}(km) = \frac{1}{|\mathcal{S}_{km}|} \sum_{t \in \mathcal{S}_{km}} I^{same} = I^{same}
\end{equation}
\end{proof}

\begin{lemma}[Cross-Column Independence]
\label{lem:cross_col}
Let $J, L \sim \text{Uniform}([m])$ be independent. Then $T_{i,J} \perp T_{k,L}$, and hence $I(T_{i,J}; T_{k,L}) = 0$.
\end{lemma}

\begin{proof}
When $J \perp L$:
\begin{align}
P(T_{i,J} = a, T_{k,L} = b) &= \sum_{j,l} P(J=j)P(L=l) P_j(a) P_l(b) \nonumber \\
&= \left(\frac{1}{m}\sum_j P_j(a)\right)\left(\frac{1}{m}\sum_l P_l(b)\right) = Q(a) Q(b)
\end{align}
Hence $T_{i,J} \perp T_{k,L}$.
\end{proof}

\subsection{Characterization of $I^{same}$}

\begin{proposition}[Characterization of Same-Column MI]
\label{prop:isame_characterization}
Under Assumptions~\ref{ass:consistency} and~\ref{ass:distinct}, in the conditional independence case ($T_{i,j} \perp T_{k,j} \mid j$):
\begin{equation}
I^{same} = D_{KL}(R \| Q \otimes Q)
\end{equation}
where $R(a,b) = \frac{1}{m}\sum_{j=1}^m P_j(a)P_j(b)$ and $Q = \frac{1}{m}\sum_j P_j$.

The magnitude of $I^{same}$ is governed by the \textbf{cross-column variance}:
\begin{equation}
\sigma^2 := \sum_a \text{Var}_j[P_j(a)] = \sum_a \left( \frac{1}{m}\sum_j P_j(a)^2 - Q(a)^2 \right)
\end{equation}
Specifically:
\begin{itemize}
    \item $I^{same} > 0$ if and only if $\sigma^2 > 0$ (i.e., columns are not all identical)
    \item $I^{same}$ increases monotonically with $\sigma^2$
    \item When columns are highly distinct (large $\sigma^2$), $I^{same}$ is correspondingly large
\end{itemize}
\end{proposition}

\begin{proof}
The expression $I^{same} = D_{KL}(R \| Q \otimes Q)$ follows directly from the proof of Lemma~\ref{lem:same_col}.

For the characterization, note from~\eqref{eq:variance_form} that $R(a,a) - Q(a)^2 = \frac{\text{Var}_j[P_j(a)]}{m}$. The KL divergence $D_{KL}(R \| Q \otimes Q)$ is determined by how much $R$ differs from $Q \otimes Q$. Since the diagonal differences $R(a,a) - Q(a)^2$ are proportional to $\text{Var}_j[P_j(a)]$, the total cross-column variance $\sigma^2 = \sum_a \text{Var}_j[P_j(a)]$ governs the magnitude of $I^{same}$.

By Assumption~\ref{ass:distinct}, $\sigma^2 > 0$, ensuring $I^{same} > 0$.
\end{proof}

\begin{remark}
The cross-column variance $\sigma^2$ can be interpreted as a measure of column heterogeneity. For example:
\begin{itemize}
    \item If all columns have the same distribution ($P_j = P$ for all $j$), then $\sigma^2 = 0$ and Assumption~\ref{ass:distinct} is violated.
    \item If columns have disjoint supports (e.g., column 1 contains only integers, column 2 contains only strings), then $\sigma^2$ is maximal and $I^{same}$ is large.
\end{itemize}
\end{remark}





\subsection{Proofs of Main Theorems}

\subsubsection{Proof of Theorem~\ref{thm:main}}
\label{app:proof_main}

\begin{proof}
This follows directly from Lemma~\ref{lem:periodic}: for any $k \in \{1, \ldots, n-1\}$, $\bar{I}_{table}(km) = I^{same} > 0$.
\end{proof}

\subsubsection{Proof of Corollary~\ref{cor:liminf}}
\label{app:proof_liminf}

\begin{proof}
For any $K \in \mathbb{Z}^+$, consider a table with $n > K$ rows. By Theorem~\ref{thm:main}, $\bar{I}_{table}(Km) = I^{same}$. Since $K$ is arbitrary, the set $\{km : k \in \mathbb{Z}^+\}$ is unbounded, and at each such lag the average MI equals $I^{same}$. Therefore:
\begin{equation}
\liminf_{d \to \infty} \bar{I}_{table}(d) \geq I^{same} > 0
\end{equation}
\end{proof}

\subsubsection{Proof of Corollary~\ref{cor:ratio}}
\label{app:proof_ratio}

\begin{proof}
By Theorem~\ref{thm:main}, $\bar{I}_{table}(km) = I^{same} > 0$ for all $k \in \mathbb{Z}^+$. By the power-law assumption~\eqref{eq:powerlaw}, $I_{text}(km) \sim C(km)^{-\alpha} \to 0$ as $k \to \infty$. Hence:
\begin{equation}
\lim_{k \to \infty} \frac{\bar{I}_{table}(km)}{I_{text}(km)} = \lim_{k \to \infty} \frac{I^{same}}{C(km)^{-\alpha}} = +\infty
\end{equation}
\end{proof}

\subsubsection{Proof of Theorem~\ref{thm:eff_dist}}
\label{app:proof_eff}

\begin{proof}
\textbf{Part 1 (Table data):}
For any $\tau < I^{same}$ and any $K \in \mathbb{Z}^+$, consider a table with $n > K$ rows. By Lemma~\ref{lem:periodic}:
\begin{equation}
\bar{I}_{table}(Km) = I^{same} > \tau
\end{equation}
Since $K$ is arbitrary:
\begin{equation}
D_{eff}^{table}(\tau) = \sup\{d : \bar{I}_{table}(d) \geq \tau\} = +\infty
\end{equation}

\textbf{Part 2 (Natural language):}
Under power-law decay $I_{text}(d) \sim C d^{-\alpha}$, for any $\tau > 0$:
\begin{equation}
I_{text}(d) < \tau \quad \text{for all } d > d^* := (C/\tau)^{1/\alpha}
\end{equation}
Hence $D_{eff}^{text}(\tau) \leq d^* < \infty$.
\end{proof}

\subsection{Proofs of Propositions}

\subsubsection{Proof of Proposition for Uniform Attention Requirements}
\label{app:proof_attention}

\begin{proof}
Let $W_t$ be a cell in column $c = \text{col}(t)$. The set of past tokens in the same column is $\mathcal{C}_t := \{W_s : s < t, \, \text{col}(s) = c\}$. 

For any $W_s \in \mathcal{C}_t$, both $W_s$ and $W_t$ are cells from column $c$, at different rows. By Lemma~\ref{lem:same_col}(ii):
\begin{equation}
I(W_s; W_t) = I^{same} > 0
\end{equation}
regardless of the distance $t - s$. Thus all same-column predecessors provide the same amount of information $I^{same}$ about $W_t$, requiring uniform attention across the context.
\end{proof}

\subsubsection{Proof of Proposition for Context Length Requirements}
\label{app:proof_context}

\begin{proof}
Consider any column $c \in [m]$. The cell at row 1 occupies position $m + c$ in the linearized sequence, while the cell at row $n$ occupies position $m + (n-1)m + c = m + c + (n-1)m$. Thus these two same-column cells are separated by exactly $(n-1) \cdot m$ positions.

By Lemma~\ref{lem:same_col}, this pair has mutual information $I^{same} > 0$. To capture this dependency, the model's effective context must span at least $(n-1) \cdot m$ tokens.
\end{proof}

\subsection{Auxiliary Result}

\begin{lemma}[Positive Column-Type MI]
\label{lem:type_mi}
Let $J \sim \text{Uniform}([m])$ and $T_J$ be a cell from column $J$. Under Assumptions~\ref{ass:consistency}--\ref{ass:distinct}:
\begin{equation}
I(T_J; J) > 0
\end{equation}
\end{lemma}

\begin{proof}
We have $I(T_J; J) = H(J) - H(J|T_J) = \log m - H(J|T_J)$.

By Bayes' rule: $P(J=j|T_J=v) = \frac{m P_j(v)}{\sum_l P_l(v)}$.

By Assumption~\ref{ass:distinct}, there exist $j \neq k$ and $v$ with $P_j(v) \neq P_k(v)$, so $P(J=j|T_J=v) \neq P(J=k|T_J=v)$. The posterior is non-uniform for some $v$, implying $H(J|T_J) < H(J)$, hence $I(T_J; J) > 0$.
\end{proof}