# number of partial orders modulo a fixed number

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).

• The link to the OEIS sequence A001035: oeis.org/A001035 – Pietro Majer Sep 28 '10 at 22:38
• This is a really nifty conjecture. My gut is skeptical that the period will always work out to exactly $p-1$, but even the claim that a period exists is cool. The only way I can think of approaching it is to show (for fixed $p$) that almost all posets have an automorphism of order $p$, so they don't contribute to the count mod $p$, and proving some sort of recursion for posets without such an automorphism. Good luck! – David E Speyer Sep 28 '10 at 22:53
• Since Aut(P) is a subgroup of S_n, another way to state this is that we only care about the cases where Aut(P) and S_n have the same p-sylow. In other words, we want to look at posets which are preserved by Sylow_p(S_n). Since Sylow_p(S_n) is pretty easy to describe explicitly, this might be a good starting point. – David E Speyer Sep 28 '10 at 23:08
• Ah, if I'd gone over to page 2 in the above Borevich reference, I'd have seen that your conjecture is Theorem 1. He doesn't give a detailed proof (or even a reference - apparently 'it is recounted in another place' !) but does give some hints. – dke Sep 28 '10 at 23:52
• Just to add: Borevich eventually wrote up a proof of your conjecture here springerlink.com/content/g654831527p1561v – dke Sep 29 '10 at 11:19

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?
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.