number of partial orders modulo a fixed number

Question

Let p(n) be the number of partial orders on the set {1,...,n}. From the Online Encyclopedia of Integer Sequences, we find that the known values of p(n) are {1,1,3,19,219,4231,130023,6129859,431723379,44511042511,6611065248783,1396281677105899,414864951055853499,171850728381587059351,98484324257128207032183,77567171020440688353049939,83480529785490157813844256579,122152541250295322862941281269151,241939392597201176602897820148085023}.

We see that the units digits of these numbers appear to cycle with a period of length four: 1, 3, 9, 9.

Experiments with other moduli indicate that given a prime modulus m, the sequence cycles with a period of length m-1. If the modulus m is a prime power, then the period appears to be of length phi(m), where phi is Euler's phi-function. For any modulus m, the period appears to be of length the least common multiple (LCM) of the constituent period lengths. For example, if m=12, the period appears to be of length LCM(phi(4),phi(3))=LCM(2,2)=2.

I don't know how to prove this conjecture and I don't see any reference to it. If proved, perhaps this result together with an asymptotic estimate for p(n) could be used to find higher values of p(n).

Answer 1

For q prime, enlarge $\{ 1,\cdots,m \}$ to a set of size $n=m+(q-1)$ by replacing $m$ by $q$ clones $m_1 , m_2 , \cdots , m_q$ and consider the $q$-cycle $\sigma=(m_1\ m_2\ \cdots \ m_q)$. It acts on the set of partial orders of the $n$-set and each of its orbits has size 1 or size q. Each orbit of size 1 arises from a unique partial order of the $m$-set by having all $p$ clones behave identically to the original. This proves that $p(m+(q-1)) \equiv p(m) \mod q $ I think I see how to generalize to $q^k$ but I'll have to think about it. The same idea should apply to a wider variety of structures, but which ones?

later The argument seems as if it should work for bipartite graphs on n labelled vertices and also connected bipartite graphs except for powers of 2 The data at OEIS supports this as far as it goes, ignoring the numbers for less than 3 vertices. http://www.oeis.org/A047864 http://www.oeis.org/A001832

It also works for appropriate restricted classes such as series parallel networks with n labelled vertices and parallel edges allowed. http://www.oeis.org/A053554

Here is my argument for why $p(n+\phi(q^2)) \equiv p(n) \mod q^2$. I think it generalizes to $q^k$: Further enlarge the $n$ set above to one of size $m+q^2-1=n+\phi(q^2)=N$ by replacing each clone $m_i$ by $q$ clones $m_{i1}, m_{i2}, \cdots ,m_{iq}$ and consider the $q^2$ cycle $$\tau=(m_{11}m_{21}\cdots m_{q1}m_{12}m_{22}\cdots m_{q,q})$$ It acts on partial orders of the $N$-set and the action has orbits of size 1, $q$ and $q^2$. The orbits of size less than $q^2$ are in bijective correspondence with the orbits of the same size for the action of $\sigma$ on partial orders of the $n$-set.