Pith. sign in

REVIEW 2 major objections 4 minor 46 references

Parking completions are $\mathbf{x}$-parking functions

T0 review · 2 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

Pith's one-line read Parking completions — preference lists that park around pre-occupied spots — are x-parking functions under a gap-coordinate change, and this identifies their counts with Pitman-Stanley volume polynomials.

desk verdict Answers the open problem, but the main theorem is basically the unproved Lemma 2.4 in new notation; correct and worth refereeing, though it needs a real proof of that lemma and cleanup. read the letter →

arxiv 2607.16098 v1 pith:OO6ORLH5 submitted 2026-07-17 math.CO

classification math.CO MSC 05A19
keywords parkingfunctionscompletionsx-parkingPitman-Stanleypolytopesvolumepolynomialscombinatorialenumerationpermutationinvariancegapvector
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Parking completions are the preference lists that let n−m cars all find spots after m spots have already been taken. The paper proves that these completions form exactly the same set as x-parking functions, the classic generalization of parking functions in which the i-th smallest preference is bounded by the i-th prefix sum of a vector x. The connecting x is built from the gaps between the unoccupied spots: if u is the increasing list of free spots, then x=(u1, u2−u1, ..., u_{n−m}−u_{n−m−1}). Because the count of x-parking functions is known to equal a homogeneous polynomial that also computes Pitman-Stanley polytope volumes, this set equality gives a direct explanation for why the two enumeration formulas agree, answering the open problem raised in earlier work. The proof is short: the two defining inequalities become identical under the gap substitution, and permutation invariance lifts the equality from sorted lists to all lists.

What carries the argument

The load-bearing object is the gap vector x derived from the set of unoccupied spots: with u the increasing list of free spots, set x_1=u_1 and x_i=u_i−u_{i−1}. The identity ∑_{j=1}^i x_j = u_i converts the parking-completion inequality c^↑_i ≤ u_i into the defining inequality of an x-parking function, a_i≤x1+...+xi. The second piece is permutation invariance: both parking completions and x-parking functions are unchanged as sets under reordering entries, so proving that the weakly increasing members coincide is enough to identify the full sets.

What would settle it

Compute both sides for a small case by hand: for n=4 and t=(2,4), the theorem predicts |PC_4((2,4))|=P_2((1,2))=5; list the 16 preference pairs and apply the original parking rule — any count other than 5, or any successful completion whose sorted entries exceed the free-spot bounds (1,3), would refute the claim.

Watch

Extended reading notes

Core claim

On the paper's terms, the central claim is Theorem 2.7: for any increasing list t of already occupied spots in [n], let u be the increasing list of the remaining spots and set x=(u1, u2−u1, ..., u_{n−m}−u_{n−m−1}). Then the set PC_n(t) of parking completions equals the set PF_{n−m}(x) of x-parking functions. The proof establishes the equality first for weakly increasing sequences, where the parking-completion condition c_i≤u_i and the x-parking-function condition a_i≤x1+...+xi are the same inequality after the telescoping substitution; it then uses that both families are closed under permuting entries. Corollary 2.8 records the enumeration consequence |PC_n(t)|=P_n(x), where P_n(x)=n!·V_n(x)

Load-bearing premise

The argument rests on Lemma 2.4, cited from earlier work without proof in this paper: a list c is a parking completion for occupied spots t exactly when its increasing rearrangement satisfies c^↑_i ≤ u_i, where u is the increasing list of unoccupied spots; if that characterization fails for some t, the main set equality fails with it.

Editorial extensions

If this is right

  • The number of parking completions for t equals P_n(x), where x is the gap vector of the unoccupied spots; in particular it is n! times the volume of a Pitman-Stanley polytope.
  • The two seemingly different enumeration formulas from earlier work count the same set, so their agreement is no longer numerical coincidence.
  • Known structural facts about x-parking functions transfer to parking completions, and vice versa, because the identification is a set equality rather than a statistic-preserving accident.
  • Counting completions reduces to counting weakly increasing sequences bounded by the cumulative gaps u_i; permutation symmetry contributes the multinomial factors.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the occupied pattern t and the gap vector x determine each other once n is fixed, the theorem makes parking completions and x-parking functions two labelings of one family; results can be translated between them without a new proof.
  • The enumeration consequence suggests a geometric reading the paper leaves implicit: since P_n(x) is n! times a Pitman-Stanley volume, |PC_n(t)| is an integer multiple of a polytope volume, so parking completions are a whole-number count attached to a polytope even before a lattice-point model is found.
  • A testable extension would be to compare the term counts of the two enumeration formulas as the gap vector x varies; small gaps versus large gaps likely determine which formula is shorter, giving a path to the paper's open question about computational cost.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper establishes that parking completions for a fixed occupied set t are exactly x-parking functions, where x is the vector of gaps between the unoccupied spots: x = (u_1, u_2-u_1, ..., u_{n-m}-u_{n-m-1}). This is Theorem 2.7, with Proposition 2.6 treating the weakly increasing case and Corollary 2.8 concluding that |PC_n(t)| = P_{n-m}(x), thereby giving a volume formula and resolving an open problem posed by Adeniran et al.

Significance. If fully justified, the result is a clean resolution of the open problem: it gives an identity-map bijection between parking completions and x-parking functions, explains the numerical agreements observed in [1], and connects parking completions to Pitman-Stanley volume polynomials. The exposition is readable and the computational verification for small n is a useful check. However, the main theorem is essentially a restatement of Lemma 2.4 under a change of variables, and Lemma 2.4 is quoted without proof; the paper also contains a circular alternate proof. The claimed equality is very likely correct, but as written the central proof is incomplete.

major comments (2)
  1. [§2, Lemma 2.4 and Theorem 2.7] Lemma 2.4 is the key characterization that c is a parking completion iff c^↑_i ≤ u_i for the unoccupied spots u. It is quoted from [1, Definition 2.1] but not proved, although the Introduction promises 'we include a proof of this equivalence.' This is load-bearing: with x_i = u_i - u_{i-1}, the defining condition of PF_{n-m}(x) is a^↑_i ≤ x_1+...+x_i = u_i, which is exactly Lemma 2.4. Thus Theorem 2.7 is Lemma 2.4 rewritten, and Corollary 2.8 follows immediately. Proposition 2.6 also invokes 'the inequality characterization of parking completions' in its induction step, so it does not supply the missing proof. The manuscript must either prove Lemma 2.4 from the parking algorithm or explicitly state that the main result depends on this known characterization; as written, the proof is incomplete.
  2. [§2, Proposition 2.6] The double-containment argument is not rigorous as written. The induction hypothesis is stated as 'if c=(c1,...,ck)∈PC↑_{m+k}(t), then c∈PF↑_k(x)', but PC_{m+k}(t) is not defined for a prefix of length k when t has length m; the intended total length is unclear. The step from a length-(k+1) completion d to its prefix also requires an argument that the first k entries form a parking completion for the same t. More importantly, both directions of the proof ultimately rely on Lemma 2.4: the forward direction uses it to assert d_{k+1} ≤ u_{k+1}, and the reverse direction concludes that a is a parking completion from a_i ≤ u_i, which is exactly the unproved characterization. The proposition therefore does not provide an independent derivation of the main result.
minor comments (4)
  1. [§2, Alternate proof of Lemma 2.3] The alternate proof says 'By Lemma 2.3' but the intended reference is Lemma 2.4. As printed, the alternate proof is circular. The first proof of Lemma 2.3 is fine.
  2. [§2, Proof of Theorem 2.7] The proof refers to 'Theorem 2.6' and 'Theorem 2.3'; these should be 'Proposition 2.6' and 'Lemma 2.3' respectively.
  3. [§2, Proposition 2.6] In the first containment, the conclusion is written as 'PC↑_n(x)⊆PF↑_{n-m}(x)' but should be 'PC↑_n(t)⊆PF↑_{n-m}(x)'. Later in the same proof, 'PC↑_n(x)' is again used where 'PC↑_n(t)' is meant.
  4. [§2, Remark 2.5 and Definition 2.1] The conversion between u-parking functions and x-parking functions is stated correctly, but it would help to explicitly note that x_i ∈ N since the u_i are strictly increasing positive integers; this ensures consistency with Definition 1.1.

Circularity Check

2 steps flagged · score 6.0 of 10

Main theorem reduces to the cited, unproved Lemma 2.4 by the choice of x; alternate proof of Lemma 2.3 is self-referential.

  1. other [Section 2, Alternate proof of Lemma 2.3]
    "Alternate proof of Lemma 2.3. This follows immediately from the inequality description of parking completions in Lemma 2.4. Every permutation of c has the same weakly increasing rearrangement. By Lemma 2.3, every permutation of c is a parking completion (since c itself is a parking completion)."

    The alternate proof invokes Lemma 2.3 itself to conclude that every permutation of c is a parking completion. This is a literal self-reference: the statement being proved is used as its own justification, with no independent argument supplied. Although this is presented as an alternate proof and the preceding proof is valid, it is still a circular step in the manuscript.

  2. renaming known result [Sections 1.1/2: Remark 2.5, Proposition 2.6, Theorem 2.7]
    "Define x := (u1, u2 − u1, u3 − u2, . . . , un−m − u(n−m)−1) ∈ N^N ... Observe that for all i ∈ [n], x1 + · · · + xi = ui, so 1 ≤ a↑_i ≤ ui is equivalent to 1 ≤ a↑_i ≤ x1 + · · · + xi."

    Lemma 2.4 characterizes parking completions by c↑_i ≤ u_i. Definition 1.1 and Remark 2.5 define x so that the x-parking condition is a↑_i ≤ x1+...+xi = u_i. Therefore Theorem 2.7, PC_n(t) = PF_{n−m}(x), is exactly Lemma 2.4 restated under the change of variables x_i = u_i − u_{i−1}. The proof of Proposition 2.6 invokes 'the inequality characterization of parking completions' rather than proving it, and the introduction promises a proof of Lemma 2.4 that never appears. Thus the main result is a coordinate renaming of the cited characterization, reducing to that input by construction.

full rationale

The paper's central claim is not an independent derivation from the parking-completion definition: Theorem 2.7 is obtained by quoting Lemma 2.4 from [1] and then choosing x_i = u_i − u_{i−1}. Under that choice, the x-parking inequalities are identical to the Lemma 2.4 inequalities, so the theorem is a restatement of the cited characterization in new coordinates. The introduction states 'we include a proof of this equivalence' for Lemma 2.4, but Section 2 only restates the lemma, leaving the load-bearing characterization unsupported within the paper. This is a reduction-by-construction rather than a genuinely new proof, though the underlying statement is almost certainly true and the defect is fixable by supplying or citing a complete proof of Lemma 2.4. Separately, the alternate proof of Lemma 2.3 explicitly uses Lemma 2.3 to prove itself; this is a clear circular step, but it is not load-bearing because a valid first proof of Lemma 2.3 is given. Overall, the derivation chain is partially circular: the main theorem reduces to the cited lemma by definition of x, and the manuscript contains one self-referential proof, but no fabricated data or fitted predictions are involved.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters or invented entities. The entire content is carried by the cited Lemma 2.4; the constructed x is a relabeling of the unoccupied spots, not a fitted or postulated quantity.

assumptions (3)
  • domain assumption Lemma 2.4: c in PC_n(t) iff c^↑_i <= u_i for all i, where u is the increasing arrangement of [n]\con(t).
    Attributed to Adeniran et al. [1, Definition 2.1]; this is the premise the main theorem is a restatement of, and it is not proved in the paper.
  • standard math x-parking function definition and its equivalence to u-parking functions via x_i = u_i - u_{i-1}.
    Used to identify PF with the same inequality; purely definitional.
  • standard math Permutation invariance of parking functions and x-parking functions.
    Needed to pass from weakly increasing sets to the full sets in Theorem 2.7. For parking completions it is proven in Lemma 2.3; for x-parking functions it follows from the sorted definition.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parking completions are $\mathbf{x}$-parking functions." pith.science (2026). https://pith.science/paper/OO6ORLH5

@misc{pith2026260716098,
  author       = {Pith},
  title        = {Pith review of: Parking completions are $\mathbfx$-parking functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OO6ORLH5}},
  note         = {Machine review of arXiv:2607.16098}
}
abstract

Parking functions correspond with preferences of $n$ cars which enter sequentially to park on a one-way street where (1) each car parks in the first available spot greater than or equal to its preference and (2) all cars successfully park. We generalize parking functions to parking completions: Here, we are given that some cars have already parked in a set of spots, which are indexed in a sequence $\mathbf{t}$. We then consider a preference list $\mathbf{c}$, where length of $\mathbf{t}$ + length of $\mathbf{c}$ = $n$. If all cars can park, we say that $\mathbf{c}$ is a parking completion. Adeniran et al. (2020) state an open problem which proposes a connection between the number of parking completions to the volumes of Pitman-Stanley polytopes by explicit computation on small values of $n$. In this paper, we provide a solution to this open problem by proving a theorem which explains that the set of parking completions is the set of $\mathbf{x}$-parking functions.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

46 extracted references · 4 canonical work pages

  1. [1]

    Aoki, Calcul exponentiel des op\'erateurs microdifferentiels d'ordre infini

    T. Aoki, Calcul exponentiel des op\'erateurs microdifferentiels d'ordre infini. I, Ann. Inst. Fourier (Grenoble) 33 (1983), 227--250

  2. [2]

    Brown, On a conjecture of Dirichlet, Amer

    R. Brown, On a conjecture of Dirichlet, Amer. Math. Soc., Providence, RI, 1993

  3. [3]

    R. A. DeVore, Approximation of functions, Proc. Sympos. Appl. Math., vol. 36, Amer. Math. Soc., Providence, RI, 1986, pp. 34--56

  4. [4]

    and Elder, J

    Aguilar-Fraga, T. and Elder, J. and Garcia, R. E. and Hadaway, K. P. and Harris, P. E. and Harry, K. J. and Hogan, I. B. and Johnson, J. and Kretschmann, J. and Lawson-Chavanu, K. and Mart\'inez Mori, J. C. and Monroe, C. D. and Qui\ nonez, D. and Tolson, III, D. and Williams, II, D. A. , TITLE =. Discrete Math. Theor. Comput. Sci. , FJOURNAL =. [2024--20...

  5. [5]

    Ehrenborg, Richard and Happ, Alex , TITLE =. Amer. Math. Monthly , FJOURNAL =. 2016 , NUMBER =. doi:10.4169/amer.math.monthly.123.10.1045 , URL =

  6. [6]

    Spiro, Sam , TITLE =. J. Integer Seq. , FJOURNAL =. 2019 , NUMBER =

  7. [7]

    2018, retrieved October 8, 2020 , note=

    Parking Functions , author=. 2018, retrieved October 8, 2020 , note=

  8. [8]

    2020 , eprint=

    Counting k-Naples parking functions through permutations and the k-Naples area statistic , author=. 2020 , eprint=

Show all 46 references
  1. [9]

    2023 , eprint=

    Unbounded matroids , author=. 2023 , eprint=

  2. [10]

    Butler and R

    S. Butler and R. Graham and C. Yan , year =. Parking distributions on trees , volume =. European Journal of Combinatorics , doi =

  3. [11]

    Christensen and P

    A. Christensen and P. E. Harris and Z. Jones and M. Loving and A. Ramos Rodr\'. A generalization of parking functions allowing backward movement , volume =. The Electronic Journal of Combinatorics , doi =. 2020 , pages =

  4. [12]

    Novelli and J.Y

    J.C. Novelli and J.Y. Thibon , year=. Hopf Algebras of m-permutations, (m+1)-ary trees, and m-parking functions , eprint=

  5. [13]

    and DeMuse, R

    Colaric, E. and DeMuse, R. and Martin, J. and Yin, M. , year=. Interval parking functions , eprint=. ArXiv , primaryClass=

  6. [14]

    and Elder, J

    Celano, K. and Elder, J. and Hadaway, K. P. and Harris, P. E. and Priestley, A. and Udell, G. , title=. FPSAC , year=

  7. [15]

    P. J. Cameron and D. Johannsen and T. Prellberg and P. Schweitzer , year=. Counting Defective Parking Functions , eprint=. ArXiv , primaryClass=

  8. [16]

    Shales , title=

    N. Shales , title=. retrieved October 10, 2020 , note =

  9. [17]

    Adeniran and S

    A. Adeniran and S. Butler and G. Dorpalen-Barry and P. E. Harris and C. Hettle and Q. Liang and J. L. Martin and H. Nam , year =. Enumerating Parking Completions using. The Electronic Journal of Combinatorics , doi =

  10. [18]

    , year =

    OEIS Foundation Inc. , year =. A generalization of parking functions with backward movement , volume =. The On-Line Encyclopedia of Integer Sequences , doi =

  11. [19]

    Konheim and B

    A. Konheim and B. Weiss , title =. SIAM Journal on Applied Mathematics , volume =. 1966 , doi =

  12. [20]

    Carlson and A

    J. Carlson and A. Christensen and P. E. Harris and Z. Jones and A. Ramos Rodr\'. Parking. 2020 , journal=

  13. [21]

    K. P. Hadaway and P. E. Harris , year=. Girls' Angle Bulletin , note=

  14. [22]

    2021 , journal=

    Building an online academic profile begins with your website , author=. 2021 , journal=

  15. [23]

    K. P. Hadaway and P. E. Harris , year=. The

  16. [24]

    Notick , year=

    M. Notick , year=. A Bijective Proof of a Major Index Theorem of Garsia and Gessel , eprint=. ArXiv , primaryClass=

  17. [25]

    P. R. F. Schumacher , year =. Descents in. The Electronic Journal of Combinatorics , doi =

  18. [26]

    Anderson, P. X. and Banaian, E. and Ferreri, M. J. and Goff, O. C. and Hadaway, K. P. and Harris, P. E. and Harry, K. J. and Mayers, N. and Wang, S. and Wilson, A. N. , year=. The support of. 2412.16820 , journal=

  19. [27]

    , year =

    Cayley, A. , year =. On the analytical forms called trees, second part , volume =. Philosophical Magazine , doi =

  20. [28]

    Stanley, R. P. and Pitman, J. , TITLE =. Discrete Comput. Geom. , FJOURNAL =. 2002 , NUMBER =. doi:10.1007/s00454-002-2776-6 , URL =

  21. [29]

    Hanada, J

    M. Hanada, J. Lentfer, and A. R. Vindas-Mel\'endez , TITLE =. Ann. Comb. , FJOURNAL =. 2024 , NUMBER =. doi:10.1007/s00026-023-00671-1 , URL =

  22. [30]

    Bunge, R. C. and Darrow, Jr., B. D. and El-Zanati, S. I. and Hadaway, K. P. and Pryor, M. K. and Romer, A. J. and Squires, A. and Stover, A. C. , TITLE =. Australas. J. Combin. , FJOURNAL =. 2021 , PAGES =

  23. [31]

    and Cox, C

    Brennan, Z. and Cox, C. and Curtis, B. A. and Gomez-Leos, E. and Hadaway, K. P. and Hogben, L. and Thompson, C. , TITLE =. Electron. J. Linear Algebra , FJOURNAL =. 2023 , PAGES =. doi:10.13001/ela.2023.7579 , URL =

  24. [32]

    Albright and K

    C. Albright and K. P. Hadaway and A. Holcombe Pomerance and J. Jeffries and K. J. Lorenzen and A. K. Nix , year=. On the Edge Derivative of the Normalized. ArXiv , primaryClass=. 2211.01495 , archivePrefix=

  25. [33]

    2024 , eprint=

    Lucky cars and lucky spots in parking functions , author=. 2024 , eprint=

  26. [34]

    2025 , eprint=

    Kohnert posets and polynomials of northeast diagrams , author=. 2025 , eprint=

  27. [35]

    2025 , eprint=

    Statistics on -interval parking functions , author=. 2025 , eprint=

  28. [36]

    2025 , eprint=

    Inversions in parking functions , author=. 2025 , eprint=

  29. [37]

    Hadaway, K. P. , year =. On

  30. [38]

    Yan, Catherine Huafei , TITLE =. Congr. Numer. , FJOURNAL =. 2000 , PAGES =

  31. [39]

    , TITLE =

    Kostant, B. , TITLE =. Proc. Nat. Acad. Sci. U.S.A. , FJOURNAL =. 1958 , PAGES =. doi:10.1073/pnas.44.6.588 , URL =

  32. [40]

    Kostant’s partition function and magic multiplex juggling sequences , author=. Ann. Comb. , volume=. 2020 , publisher=

  33. [41]

    Walter and B

    M. Walter and B. Doran and D. Gross and M. Christandl , year=. Entanglement. 1208.0365 , journal=

  34. [42]

    and Doran, B

    Christandl, M. and Doran, B. and Walter, M. , TITLE =. 2012. 2012 , ISBN =

  35. [43]

    and Vergne, M

    Baldoni, V. and Vergne, M. , TITLE =. J. Symbolic Comput. , FJOURNAL =. 2018 , PAGES =. doi:10.1016/j.jsc.2017.03.005 , URL =

  36. [44]

    Barvinok, A. I. , TITLE =. Math. Oper. Res. , FJOURNAL =. 1994 , NUMBER =. doi:10.1287/moor.19.4.769 , URL =

  37. [45]

    Mulmuley, K. D. and Sohoni, M. , TITLE =. SIAM J. Comput. , FJOURNAL =. 2001 , NUMBER =. doi:10.1137/S009753970038715X , URL =

  38. [46]

    H. S. Wilf , year =. Generatingfunctionology , publisher =

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.