número de órdenes parciales módulo un número fijo

Question

Sea p(n) el número de órdenes parciales en el conjunto {1,...,n}. A partir de la Enciclopedia Online de Secuencias Enteras, encontramos que los valores conocidos de p(n) son {1,1,3,19,219,4231,130023,6129859,431723379,44511042511,6611065248783,1396281677105899,414864951055853499,171850728381587059351, 98484324257128207032183,77567171020440688353049939,83480529785490157813844256579,122152541250295322862941281269151,241939392597201176602897820148085023}.

Vemos que los dígitos de las unidades de estos números parecen ciclar con un período de longitud cuatro: 1, 3, 9, 9.

Los experimentos con otros módulos indican que, dado un módulo primo m, la secuencia tiene un período de longitud m-1. Si el módulo m es una potencia prima, entonces el período parece ser de longitud phi(m), donde phi es la función phi de Euler. Para cualquier módulo m, el periodo parece tener la longitud del mínimo común múltiplo (LCM) de las longitudes de los periodos constitutivos. Por ejemplo, si m=12, el período parece tener una longitud LCM(phi(4),phi(3))=LCM(2,2)=2.

No sé cómo demostrar esta conjetura y no veo ninguna referencia a ella. Si se demuestra, tal vez este resultado junto con una estimación asintótica para p(n) podría utilizarse para encontrar valores más altos de p(n).

Answer 1

Para q primo, ampliar $\{ 1,\cdots,m \}$ a un conjunto de tamaño $n=m+(q-1)$ sustituyendo $m$ por $q$ clones $m_1 , m_2 , \cdots , m_q$ y considerar la $q$ -ciclo $\sigma=(m_1\ m_2\ \cdots \ m_q)$ . Actúa sobre el conjunto de órdenes parciales del $n$ -y cada una de sus órbitas tiene tamaño 1 o tamaño q. Cada órbita de tamaño 1 surge de un único orden parcial del $m$ -conjunto al tener todos los $p$ Los clones se comportan de forma idéntica al original. Esto demuestra que $p(m+(q-1)) \equiv p(m) \mod q$ Creo que veo cómo generalizar a $q^k$ pero tendré que pensarlo. La misma idea debería aplicarse a una mayor variedad de estructuras, pero ¿cuáles?

más tarde El argumento parece que debería funcionar para los grafos bipartitos sobre n vértices etiquetados y también para los grafos bipartitos conectados excepto para las potencias de 2 Los datos de la OEIS lo corroboran en la medida de lo posible, ignorando los números de menos de 3 vértices. http://www.oeis.org/A047864 http://www.oeis.org/A001832

También funciona para clases restringidas adecuadas, como las redes paralelas en serie con n vértices etiquetados y aristas paralelas permitidas. http://www.oeis.org/A053554

Aquí está mi argumento de por qué $p(n+\phi(q^2)) \equiv p(n) \mod q^2$ . Creo que se generaliza a $q^k$ : Ampliar aún más el $n$ ajustado arriba a uno de tamaño $m+q^2-1=n+\phi(q^2)=N$ sustituyendo cada clon $m_i$ por $q$ clones $m_{i1}, m_{i2}, \cdots ,m_{iq}$ y considerar la $q^2$ ciclo $$\tau=(m_{11}m_{21}\cdots m_{q1}m_{12}m_{22}\cdots m_{q,q})$$ Actúa sobre órdenes parciales del $N$ -y la acción tiene órbitas de tamaño 1, $q$ y $q^2$ . Las órbitas de tamaño inferior a $q^2$ están en correspondencia biyectiva con las órbitas del mismo tamaño para la acción de $\sigma$ en órdenes parciales del $n$ - conjunto.