Congruences of concave composition functions

Keenan Monks, Lynnelle Ye

Published 2014-07-04Version 1

Concave compositions are ordered partitions whose parts are decreasing towards a central part. We study the distribution modulo $a$ of the number of concave compositions. Let $c(n)$ be the number of concave compositions of $n$ having even length. It is easy to see that $c(n)$ is even for all $n\geq1$. Refining this fact, we prove that $$\#\{n<X:c(n)\equiv 0\pmod 4\}\gg\sqrt{X}$$ and also that for every $a>2$ and at least two distinct values of $r\in\{0,1,\dotsc,a-1\}$, $$\#\{n<X: c(n)\equiv r\pmod{a}\} > \frac{\log_2\log_3 X}{a}.$$ We obtain similar results for concave compositions of odd length.