Tamizado cíclico

En matemáticas combinatorias , el cribado cíclico es un fenómeno en el que un polinomio entero evaluado en ciertas raíces de la unidad cuenta las simetrías rotacionales de un conjunto finito . ^{[ 1 ]} Dada una familia de fenómenos de cribado cíclico, los polinomios dan un q -análogo para la enumeración de los conjuntos y a menudo surgen de una estructura algebraica subyacente, como una representación .

El primer estudio sobre el tamizado cíclico fue publicado por Reiner, Stanton y White en 2004. ^{[ 2 ]} El fenómeno generaliza el " fenómeno q = −1" de John Stembridge , que considera evaluaciones del polinomio solo en la primera y segunda raíz de la unidad (es decir, q = 1 y q = −1). ^{[ 3 ]}

Para cada entero positivo${\displaystyle n}$, dejar${\displaystyle \omega _{n}}$denota lo primitivo${\displaystyle n}$^{raíz cuadrada} de la unidad${\displaystyle e^{2\pi i/n}}$.

Dejar${\displaystyle X}$sea ​​un conjunto finito con una acción del grupo cíclico${\displaystyle C_{n}}$y dejar${\displaystyle f(q)}$sea ​​un polinomio entero . La tripleta${\displaystyle (X,C_{n},f(q))}$exhibe el fenómeno de tamizado cíclico (o CSP ) si para cada entero positivo${\displaystyle d}$divisor${\displaystyle n}$, el número de elementos en${\displaystyle X}$fijado por la acción del subgrupo${\displaystyle C_{d}}$de${\displaystyle C_{n}}$es igual a${\displaystyle f(\omega _{d})}$. Si${\displaystyle C_{n}}$actúa como rotación por${\displaystyle 2\pi /n}$, esto cuenta elementos en${\displaystyle X}$con${\displaystyle d}$simetría rotacional de pliegue .

De forma equivalente, supongamos que${\displaystyle \sigma :X\to X}$es una biyección en${\displaystyle X}$de tal manera que${\displaystyle \sigma ^{n}={\rm {id}}}$, dónde${\displaystyle {\rm {id}}}$es el mapa de identidad. Entonces${\displaystyle \sigma }$induce una acción de${\displaystyle C_{n}}$en${\displaystyle X}$donde un generador dado${\displaystyle c}$de${\displaystyle C_{n}}$actos por${\displaystyle \sigma }$. Entonces${\displaystyle (X,C_{n},f(q))}$exhibe el fenómeno de tamizado cíclico si el número de elementos en${\displaystyle X}$arreglado por${\displaystyle \sigma ^{d}}$es igual a${\displaystyle f(\omega _{n}^{d})}$para cada entero${\displaystyle d}$.

Dejar${\displaystyle X}$sean los subconjuntos de 2 elementos de${\displaystyle \{1,2,3,4\}}$Definir una biyección${\displaystyle \sigma :X\to X}$lo que incrementa cada elemento del par en uno (y envía${\displaystyle 4}$volver a${\displaystyle 1}$). Esto induce una acción de${\displaystyle C_{4}}$en${\displaystyle X}$, que tiene una órbita$${\displaystyle \{1,3\}\mapsto \{2,4\}\mapsto \{1,3\}}$$ de tamaño dos y una órbita $${\displaystyle \{1,2\}\mapsto \{2,3\}\mapsto \{3,4\}\mapsto \{1,4\}\mapsto \{1,2\}}$$ de talla cuatro. Si${\displaystyle f(q)=1+q+2q^{2}+q^{3}+q^{4}}$, entonces${\displaystyle f(1)=6}$es el número de elementos en${\displaystyle X}$,${\displaystyle f(i)=0}$cuenta puntos fijos de${\displaystyle \sigma }$,${\displaystyle f(-1)=2}$es el número de puntos fijos de${\displaystyle \sigma ^{2}}$, y${\displaystyle f(-i)=0}$es el número de puntos fijos de${\displaystyle \sigma ^{3}}$. Por lo tanto, el triple${\displaystyle (X,C_{4},f(q))}$presenta el fenómeno de tamizado cíclico.

En términos más generales, se establece${\displaystyle [n]_{q}:=1+q+\cdots +q^{n-1}}$y definimos el coeficiente q- binomial mediante $${\displaystyle \left[{n \atop k}\right]_{q}={\frac {[n]_{q}\cdots [2]_{q}[1]_{q}}{[k]_{q}\cdots [2]_{q}[1]_{q}[n-k]_{q}\cdots [2]_{q}[1]_{q}}}.}$$ que es un polinomio entero que se evalúa al coeficiente binomial usual en${\displaystyle q=1}$Para cualquier entero positivo${\displaystyle d}$divisor${\displaystyle n}$,

${\displaystyle \left[{n \atop k}\right]_{\omega _{d}}={\begin{cases}\left({n/d \atop k/d}\right)&{\text{if }}d\mid k,\\0&{\text{otherwise}}.\end{cases}}}$

Si${\displaystyle X_{n,k}}$es el conjunto de tamaño-${\displaystyle k}$subconjuntos de${\displaystyle \{1,\dots ,n\}}$con${\displaystyle C_{n}}$actuando incrementando cada elemento del subconjunto en uno (y enviando${\displaystyle n}$volver a${\displaystyle 1}$), y si${\displaystyle f_{n,k}(q)}$es el coeficiente q -binomial anterior, entonces${\displaystyle (X_{n,k},C_{n},f_{n,k}(q))}$exhibe el fenómeno de tamizado cíclico para cada${\displaystyle 0\leq k\leq n}$. ^{[ 4 ]}

El fenómeno del tamizado cíclico puede enunciarse naturalmente en el lenguaje de la teoría de la representación. La acción grupal de${\displaystyle C_{n}}$en${\displaystyle X}$se extiende linealmente para obtener una representación, y la descomposición de esta representación en irreducibles determina los coeficientes requeridos del polinomio.${\displaystyle f(q)}$. ^{[ 5 ]}

Dejar${\displaystyle V=\mathbb {C} (X)}$Sea el espacio vectorial sobre los números complejos con una base indexada por un conjunto finito.${\displaystyle X}$. Si el grupo cíclico${\displaystyle C_{n}}$actúa en${\displaystyle X}$, luego extendiendo linealmente cada acción se convierte en${\displaystyle V}$en una representación de${\displaystyle C_{n}}$.

Para un generador${\displaystyle c}$de${\displaystyle C_{n}}$, su acción sobre${\displaystyle \mathbb {C} (X)}$viene dada por una matriz de permutación${\displaystyle [c]}$y el rastro de${\displaystyle [c]^{d}}$cuenta los elementos de${\displaystyle X}$arreglado por${\displaystyle c^{d}}$. En particular, el triple${\displaystyle (X,C_{n},f(q))}$exhibe el fenómeno de tamizado cíclico si y solo si${\displaystyle f(\omega _{n}^{d})=\chi (c^{d})}$por cada${\displaystyle 0\leq d<n}$, dónde${\displaystyle \chi }$es el carácter de${\displaystyle V}$.

Esto proporciona un método para determinar${\displaystyle f(q)}$. Para cada entero${\displaystyle k}$, dejar${\displaystyle V^{(k)}}$ser la representación unidimensional de${\displaystyle C_{n}}$en el cual${\displaystyle c}$actúa como una multiplicación escalar por${\displaystyle \omega _{n}^{k}}$. Para un polinomio entero${\textstyle f(q)=\sum _{k\geq 0}m_{k}q^{k}}$, el triple${\displaystyle (X,C_{n},f(q))}$exhibe el fenómeno de tamizado cíclico si y solo si $${\displaystyle V\cong \bigoplus _{k\geq 0}m_{k}V^{(k)}.}$$