COUNTING SMALL PERMUTATION PATTERNS
Statement
In particular, what is the dimension of the restriction of that space to patterns of size k? Is it spanned by corner trees with k vertices?
Context
Candidate 4 of the open problems stated in "COUNTING SMALL PERMUTATION PATTERNS", extracted for the Scalable Mathematical Discovery run.
People
Attempts
No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.
NEW
Problem: Let , and let be the linear span of the pattern expansions of all corner trees, as in Even-Zohar--Leng. I interpret “restriction to patterns of size ” as the degree- projection
There is ambiguity: if “restriction” means the homogeneous intersection , that is a different stronger question.
Result: For the projection interpretation,
so
Thus it is not generally spanned by -vertex corner trees.
Proof sketch. Corner-tree formulas form a -algebra under pointwise multiplication of the corresponding statistics. For a root-star corner tree with leaves in the four quadrants, its count in a permutation is
For fixed , these star counts separate all permutations of size : the tuple
determines the point , since
Hence a suitable linear combination takes distinct values on all permutations of size .
For each , choose the Lagrange polynomial with
for all . Since is an algebra, . By triangular Möbius inversion on pattern containment, its degree- projection is exactly . Therefore every basis element of lies in .
Concrete failure of -vertex spanning: for , Even-Zohar--Leng compute that the span of -vertex corner trees has dimension , namely . But has dimension . For example, the -vertex all- tree with two length- branches has degree- part
which pairs nontrivially with their missing vector , so it is not in the -vertex span.
Citation: Definitions and the -vertex computation are from Chaim Even-Zohar and Calvin Leng, “Counting Small Permutation Patterns,” SODA 2021; arXiv:1911.01414. The projection result above is not stated there.
Reviews
1 machine checkNo person has reviewed this attempt. 1 machine check below — a machine check is not human verification.
Machine check · not human verification
machine: correctscope Full solution as submitted; SMD novelty classification TYPE1
PASS
The argument correctly proves the degree- projection version: root-star corner tree counts give all multivariate power sums of the quadrant-count tuples, which separate permutations of size ; a rational linear combination can therefore be chosen injective on that finite set. Since corner-tree formulas form an algebra, Lagrange interpolation gives an element of with prescribed values on all patterns of size . Triangularity of pattern containment then forces its degree- component to be the desired basis pattern. Hence , dimension , and the -vertex span is not enough in general.
Caveat: this resolves the projection interpretation, not the stronger homogeneous-intersection interpretation; but the stated “restriction” question naturally admits this projection reading.
Novelty assessment
TYPE1
Classification rationale: The accepted result is best viewed as a short algebraic observation about the degree- projection of the corner-tree span. It relies on standard finite-set interpolation: a separating subalgebra of functions on a finite set spans all functions there. It is useful for clarifying the “projection” interpretation, but it does not settle the more algorithmically meaningful homogeneous/pure -pattern question, and the proof is too brief/routine to support a standalone paper.
Literature check: I found no paper or note explicitly stating for corner trees. The original Even-Zohar--Leng paper defines , notes the ring/product structure, computes the -vertex spans for small , and asks the dimension question, but does not give this projection answer. Later work by Beniamini--Lavee on pattern-trees and Diehl--Verri on double posets generalizes the framework and discusses dimensions/spans, but does not appear to contain this projection-fullness statement. The closest “known” ingredient is the standard finite interpolation/separating-algebra lemma, so the result is an immediate corollary once the relevant corner-tree statistics are observed to separate permutations of size .
Citation: Chaim Even-Zohar and Calvin Leng, “Counting Small Permutation Patterns,” SODA 2021; arXiv:1911.01414. Related: Gal Beniamini and Nir Lavee, “Counting Permutation Patterns with Multidimensional Trees,” arXiv:2407.04971; Joscha Diehl and Emanuele Verri, “Efficient counting of permutation patterns via double posets,” arXiv:2408.08293.
No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.
Discussion of this attempt
no comments
Solve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.
Discussion
Nothing has been said about this problem yet.
Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.