A very small combinatorics problem
In today’s post, I’d like to discuss a relatively simple combinatorics problem. This problem is quite elementary and admits a number of solutions, but I’d like to highlight a visual interpretation that I have enjoyed for many years.
Suppose p is prime, k is a positive integer, and 1 ≤ n ≤ p^k – 1. What is (p^k choose n), modulo p?
This is fairly straightforward to calculate in multiple ways. Although I haven’t worked through these arguments, I believe you can pull out a factor of p^k/n from the binomial coefficient and stratify into the cases where p and n are or are not relatively prime. Similarly, there may be a clean argument using generating functions. However, I’ll outline a nice way to “geometrically” interpret this problem. (Admittedly, I’m pretty sure this can be framed as the trivial corollary of a couple basic results in group theory!)
I would also like to post more detailed mathematical content in the future, so please consider this post to be a gentle warm-up. My apologies if you find this too long-winded!
(Please note that I am currently looking for employment; see the end of this post for further details.)
Introduction
Let’s define the set of integers modulo p^k – 1 and call it R = {0, 1, …, p^k – 1}. Then (p^k choose n) is, from the direct combinatorial interpretation of the binomial coefficient, the number of distinct subsets of R with cardinality n.
Define a “rotation function” f that acts on elements of R as f(s) = s + p^(k-1). In essence, you can imagine R as a circle of p^k numbers, where if you apply f to some subset of that circle, it rotates that subset a distance p^(k-1) around the circle. Notice that application of f p times gives you the identity. We will call one application of f a “rotation.”
Given some subset S of R, we can ask the following question: when you apply f repeatedly to S, how many distinct sets do you generate? Let’s call this number the orbit of S, and let’s call the length of an orbit the smallest positive integer i such that applying f i times to S gives you S itself. We can immediately see that if the length of the orbit of some set S is L, then 0 < L ≤ p, because by construction, rotating any element around the “circle” of R p times will give you that same element back.
In this setup, we can classify subsets S of R with cardinality n in terms of the length of their orbit L. We will first show that L must divide p, so that either L = 1 or L = p. We will then analyze each of those two cases individually.
Either L = 1 or L = p
Suppose that there is a subset S of R with an orbit of length L. Assume that L does not divide p, i.e., we can write p = bL + c for positive integers b, c where c < L. Suppose we rotate S bL times, giving us back S itself. Then suppose we rotate S L additional times, again giving us back S. However, notice that we have now “wrapped around the circle,” because by construction (b + 1)L is greater than p. In particular, performing (b + 1)L rotations is the same as performing L – c rotations. Therefore performing L’ = L – c < L rotations on S also yields S, contradicting the original assumption that L is the length of the orbit of S.
Because L must divide p and p is prime, we have either L = 1 or L = p.
Subsets with orbits of length p
Notice that because such subset has an orbit of length p, we should expect there to be a great deal of “redundancy” within these subsets in the sense that some of these subsets should generate the remainder of them when rotated sufficiently many times. In particular, we can divide up these subsets into collections of size p, where within each collection, any given set will generate the other p – 1 sets when rotated 1, 2, …, p – 1 times. Intuitively, these collections should be totally disjoint from one another, and there should be no subset which does not belong to exactly one such collection. Therefore, the total number of such subsets is a multiple of p, hence equal to 0 modulo p.
For clarity, the above figure demonstrates an p = 3 situation where a subset of n = 3 points is being rotated around the circle of numbers R.
Subsets with orbits of length 1
By definition, subsets with orbits of length 1 remain unchanged after applications of f. Suppose that we have such a subset S. For f(S) = S, it must be true that f(s) is also a member of S for all s ∈ S. Because the orbit of any single element is equal to p, we must have at least p elements in S.
The above figure illustrates three different examples of choosing subsets of n = 4 points where each subset remains unchanged after arbitrarily many rotations. Here p = 4.
Intuitively, we immediately see that we can also form subsets of cardinality greater than p with L = 1 by taking unions of different subsets of cardinality p and L = 1. For example, suppose that we take the union of the subsets depicted in the left and middle rings above, giving us the following subset of n = 8 points, also invariant under applications of f:
Furthermore, if we took the union of all three of the n = 4 subsets depicted above, that would give us an n = 12 subset with L = 1, and so on and so forth.
Notice that because each of the “base” subsets has cardinality p, any “higher-order” subsets we construct must have a cardinality which is a multiple of p. Therefore, if p does not divide n, then the number of subsets of cardinality n with L = 1 is zero.
Alternatively, suppose that p does divide n. Notice that if we choose n/p points in any arbitrary region of length q, rotating those points p – 1 times will generate a valid subset of cardinality n and L = 1. (Intuitively, each application of f “moves” the n/p points into the next region of length q, and after p – 1 rotations we end up with a subset of size n.) Therefore, the number of valid subsets is the same as the number of ways to choose n/p points from q points, where we assume an arbitrary division of R into contiguous subsets of q points (the exact divisions do not matter). I.e., the number of valid subsets is equal to (q choose n/p) = (p^(k – 1) choose n/p).
Wrapping things up
We know that the number of subsets of R with cardinality n and length p is equal to 0 modulo p. Call this number A. We also know that the number of subsets of R with cardinality n and length p is equal to either 0 or (p^(k – 1) choose n/p). Call this number B. Finally, we know that there are no other subsets of R with cardinality n.
If A = 0 mod p and B = 0, then we are finished: (p^k choose n) = 0 mod p.
If A = 0 mod p and B = (p^(k – 1) choose n/p), then (p^k choose n) = (p^(k – 1) choose n/p) mod p. However, we can apply the exact same argument outlined above to show that this is itself congruent to either 0 or (p^(k – 2) choose n/p^2) mod p, and so on and so forth. As we follow this recursive argument, we either terminate when we find that the entire expression is congruent to 0 mod p, or we reach the base case of (p choose n/p^k). Since (p choose z) is divisible by p for all z where 1 ≤ z ≤ p – 1, this base case is also congruent to 0 mod p.
Future articles
I’d like to write more technical content in the future. Some potential topics are listed below; let me know if you have any suggestions.
- Review of the series of papers by Guillermo et al. which supply definitions and some basic results for formal analysis of AMMs and CFMMs
- Review of elementary proofs of Hilbert’s Nullstellensatz and its significance
- Review of scientific topics such as a basic introduction to density functional theory
- Review of protocol whitepapers generally as they catch my attention
In general, I’d like to catch up to the state of the art on DeFi theory over the next several months and hopefully do some original research in the area.
Employment
Please note that I am currently looking for employment and am happy to receive inquiries through Twitter DMs: https://twitter.com/0xfbifemboy
I have a technical background with professional expertise in statistical methodology and machine learning. I am proficient in R, Julia, and Python, with moderate competency in C++, and am novice-level in Solidity and Rust (but hopefully learning fast). My ideal role is research-based with a theoretical or mathematical component but also with the opportunity to learn from more experienced DeFi developers.
I’m particularly interested in novel protocols which are pushing forward the cutting edge of on-chain finance from both theoretical and practical perspectives.
Leave a Reply