Four diagonals suffice: completeness of Parikh matrices when letters occur at most twice

The Parikh matrix of a word over an ordered alphabet records, diagonal by diagonal, the numbers of occurrences of the scattered subwords made of consecutive letters. For permutations the pair counts on the third diagonal determine the whole matrix (the completeness theorem of the author’s 2006 thesis, and a special case of Salomaa’s $\gamma$-property theorem of 2005), while Salomaa showed that in general no fixed number of diagonals suffices. We prove that if every letter other than the first and the last letter of the alphabet occurs at most twice, the first four diagonals determine the Parikh matrix, and we give the long counts explicitly: the count of $j(j+1)\cdots l$ factorises across every edge $e$ at which $w$ avoids the scattered subword $e(e+1)e(e+1)$, and along a chain of interleaved pairs it is a bilinear expression in four counts of length $2$ and $3$. This proves, for such words, a statement that Salomaa reports was sometimes conjectured in general, and it contains Simpson’s result for palindromes in which every letter occurs twice; in particular, the Parikh classes of words in which each letter occurs twice are the sets of words with given third and fourth diagonals. Salomaa’s construction shows that counts of length at most $n$ do not suffice when the inner letters occur $n$ times; we show that one copy of the first letter is enough, giving for every $n\ge2$ two words of content $(1,n,\dots,n)$ whose Parikh matrices differ only in the corner. Their window counts are ballot numbers, among them the Catalan number $C_n$, by a reflection argument. We conjecture that counts of length at most $n+1$ always suffice when the inner letters occur at most $n$ times, and support it by exhaustive computation for $n=3$ and $n=4$. The main theorem, the rectangle rule, the crossing chain and the corner statement of the sharpness family for $n=3,4$ are formalised in Lean 4 at the level of words.