pith. sign in

arxiv: 2605.18885 · v1 · pith:LX3EEICOnew · submitted 2026-05-16 · 💻 cs.IT · cs.AI· cs.CC· math.IT

The Extremum Stack is a Minimal Sufficient Statistic for Rate-Independent Functionals: A Kolmogorov Complexity Characterisation

Piotr Frydrych This is my paper

Pith reviewed 2026-05-20 14:30 UTC · model grok-4.3

classification 💻 cs.IT cs.AIcs.CCmath.IT
keywords Kolmogorov complexitysufficient statisticrate-independent functionalsextremum stackPreisach operatorhysteresistime series compressioncausal functionals
0
0 comments X

The pith

The extremum stack of a sequence is a minimal sufficient statistic for all computable causal rate-independent functionals.

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

The paper shows that the length of the shortest program able to answer any query from the class of computable causal rate-independent functionals on a sequence is bounded above and below by the Kolmogorov complexity of the sequence's extremum stack, up to an additive constant independent of length. This establishes that the stack retains exactly the information needed to compute every such functional without excess or deficit. A reader would care because it gives a precise optimality guarantee for a particular way of compressing hysteresis-driven data streams that standard methods do not supply.

Core claim

We prove that the extremum stack of a discrete sequence is a minimal sufficient statistic for the class of all computable, causal, rate-independent functionals, in the sense of Kolmogorov complexity. Specifically, we establish K(Π_n) - O(1) <= K_R(u_{0:n}) <= K(Π_n) + O(1), where K_R(u_{0:n}) is the length of the shortest program answering every query in the class R, and the O(1) overhead is independent of both the sequence length n and the stack depth k. Sufficiency follows from the classical wiping property of the Preisach hysteresis operator. Minimality is established via a finite indicator family whose rate-independence is verified explicitly.

What carries the argument

The extremum stack Π_n, a record of successive local maxima and minima that carries all information required to evaluate rate-independent functionals via the wiping property.

If this is right

  • Any compression of a sequence that preserves answers to the entire class R must keep at least K(Π_n) minus a constant bits.
  • The implied stack-based compression carries a Kolmogorov optimality guarantee that standard time-series methods lack.
  • The constant overhead remains independent of sequence length and stack depth.
  • Sufficiency holds because the Preisach operator's wiping property lets the stack reconstruct every functional output.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The result suggests that sensor streams governed by rate-independent dynamics can be losslessly compressed to the stack size while retaining full functional behavior.
  • Similar bounds may hold for other functional classes if they admit an analogous wiping or sufficient-statistic structure.
  • In practice this could guide minimal-memory implementations for hysteresis models without needing to store the full original sequence.

Load-bearing premise

The functionals must belong to the restricted class of computable causal rate-independent ones, and the minimality proof depends on explicit verification that a finite set of indicator functionals is rate-independent.

What would settle it

A single computable causal rate-independent functional whose shortest describing program is shorter than K(Π_n) minus a constant would falsify the lower bound on K_R.

read the original abstract

We prove that the extremum stack of a discrete sequence is a minimal sufficient statistic for the class of all computable, causal, rate-independent functionals, in the sense of Kolmogorov complexity. Specifically, we establish K(Pi_n) - O(1) <= K_R(u_{0:n}) <= K(Pi_n) + O(1), where K_R(u_{0:n}) is the length of the shortest program answering every query in the class R, and the O(1) overhead is independent of both the sequence length n and the stack depth k. Sufficiency follows from the classical wiping property of the Preisach hysteresis operator. Minimality is established via a finite indicator family whose rate-independence is verified explicitly. Any compression of a hysteresis-driven stream that preserves the full class R must therefore retain at least K(Pi_n) - O(1) bits; the stack-based compression algorithm implied by the result carries a Kolmogorov optimality guarantee that none of the standard time-series compression methods provide.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript proves that the extremum stack Π_n of a discrete sequence is a minimal sufficient statistic for the class R of all computable, causal, rate-independent functionals in the Kolmogorov complexity sense. It establishes the two-sided bound K(Π_n) - O(1) ≤ K_R(u_{0:n}) ≤ K(Π_n) + O(1), with the O(1) term independent of sequence length n and stack depth k. Sufficiency follows from the wiping property of the Preisach hysteresis operator, which ensures every functional in R depends only on the final stack state. Minimality is shown by an explicit finite indicator family belonging to R whose outputs recover Π_n, yielding the lower bound on K_R.

Significance. If the central bounds hold, the result supplies a Kolmogorov-optimality certificate for stack-based compression of streams generated by rate-independent operators. This distinguishes the approach from generic time-series compressors and directly links classical hysteresis theory (via the wiping property) to algorithmic information theory. The explicit construction of a finite test family and the uniform simulation argument for arbitrary members of R are notable strengths that make the claim falsifiable and potentially useful for theoretical guarantees in signal processing and control.

major comments (2)
  1. [Minimality construction (indicator family)] The lower bound relies on the indicator family being both rate-independent and causal; the manuscript should add an explicit verification (perhaps in the section constructing the family) that each indicator functional satisfies the rate-independence definition for arbitrary input sequences, as any counter-example would invalidate the recovery of Π_n and collapse the minimality claim.
  2. [Proof of lower bound] The claim that the O(1) overhead is independent of stack depth k is load-bearing for the optimality statement. The size of the indicator family grows with k; the proof must exhibit an explicit uniform bound on the program length needed to simulate the family that does not grow with k, otherwise the lower bound becomes K(Π_n) - O(log k) or worse.
minor comments (3)
  1. [Introduction] The notation K_R(u_{0:n}) is introduced in the abstract before being formally defined; a short paragraph in the introduction clarifying that it is the minimal program length answering all queries in R would improve readability.
  2. [Sufficiency argument] A reference to the original Preisach 1935 paper or a standard monograph on hysteresis operators (e.g., Mayergoyz) should be added when invoking the wiping property, to anchor the classical fact used for sufficiency.
  3. [Preliminaries] The abstract states the result for 'discrete sequence' but the full definition of rate-independence for discrete-time inputs should be stated once in the preliminaries to avoid ambiguity with continuous-time formulations.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and the detailed comments on the minimality construction and the uniformity of the Kolmogorov bound. We address each point below and will revise the manuscript accordingly to strengthen the presentation.

read point-by-point responses

  1. Referee: [Minimality construction (indicator family)] The lower bound relies on the indicator family being both rate-independent and causal; the manuscript should add an explicit verification (perhaps in the section constructing the family) that each indicator functional satisfies the rate-independence definition for arbitrary input sequences, as any counter-example would invalidate the recovery of Π_n and collapse the minimality claim.

    Authors: We agree with the referee that an explicit verification for arbitrary sequences would enhance the rigor of the minimality proof. While the current manuscript includes a verification, it may not be sufficiently detailed for all readers. In the revised manuscript, we will expand this into a dedicated proposition that directly applies the rate-independence definition to show that each indicator functional depends only on the final extremum stack state, independent of the specific sequence history. The proof will cover general cases by considering the possible orderings of extrema and invoking the wiping property of the underlying hysteresis operator. This addition will be placed in the section on the indicator family construction. revision: yes

  2. Referee: [Proof of lower bound] The claim that the O(1) overhead is independent of stack depth k is load-bearing for the optimality statement. The size of the indicator family grows with k; the proof must exhibit an explicit uniform bound on the program length needed to simulate the family that does not grow with k, otherwise the lower bound becomes K(Π_n) - O(log k) or worse.

    Authors: We thank the referee for highlighting this subtlety in the uniformity of the bound. Although the family size increases with k, the simulation program can be designed to be independent of k in its description length. We will add to the proof an explicit description of a universal program Q of fixed length (independent of k) that takes as input the value of k and the stack Π_n, and outputs the results of all indicator functionals in the family. The program Q implements a fixed algorithm to generate the family description from k without requiring additional bits proportional to k, as the generation rule is hardcoded in a constant-size manner. We will include a bound |Q| ≤ C where C is a small constant (e.g., less than 200 bits) that does not depend on k or n. This ensures the lower bound remains K(Π_n) - O(1) with the O(1) uniform over all k. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The central bounds K(Π_n) - O(1) ≤ K_R(u_{0:n}) ≤ K(Π_n) + O(1) are obtained by invoking the classical wiping property of the Preisach operator (an external result from hysteresis theory) for sufficiency and by explicit construction plus direct verification of rate-independence, causality, and computability for a finite indicator family for minimality. Neither step reduces to a self-definition, a fitted parameter renamed as prediction, or a load-bearing self-citation; the O(1) terms are independent of n and k, and the argument remains falsifiable against the stated class R without internal collapse to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard definitions from algorithmic information theory and domain properties of hysteresis operators drawn from prior literature.

axioms (2)
  • standard math Kolmogorov complexity K is well-defined and satisfies the standard inequalities for the sequences and programs considered.
    Invoked throughout the bounds in the abstract.
  • domain assumption The Preisach hysteresis operator possesses the wiping property that erases unnecessary history for rate-independent functionals.
    Used to establish sufficiency of the extremum stack.

pith-pipeline@v0.9.0 · 5712 in / 1326 out tokens · 62163 ms · 2026-05-20T14:30:42.057103+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages

  1. [1]

    George Cybenko

    M. Brokate, J. Sprekels, Hysteresis and Phase Transitions, Springer, New York, 1996.doi:10.1007/978-1-4612-4048-8

    work page doi:10.1007/978-1-4612-4048-8 1996

  2. [2]

    I.D.Mayergoyz, MathematicalModelsofHysteresis, Springer, NewYork, 1991.doi:10.1007/978-1-4612-3028-1

    work page doi:10.1007/978-1-4612-3028-1 1991

  3. [3]

    Frydrych, R

    P. Frydrych, R. Szewczyk, New portfolio risk optimisation method for strongly dependent assets, Journal of Engineering Studies and Research 20 (3) (2014) 30–37. 8

    work page 2014

  4. [4]

    Frydrych, Preisach attention: A hysteretic model of sequential mem- ory, ZenodoPreprint

    P. Frydrych, Preisach attention: A hysteretic model of sequential mem- ory, ZenodoPreprint. Under review at Neural Networks (Elsevier) (2025). doi:10.5281/zenodo.20133614. URLhttps://doi.org/10.5281/zenodo.20133614

    work page doi:10.5281/zenodo.20133614 2025

  5. [5]

    M. Li, P. Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd Edition, Springer, New York, 2008.doi:10.1007/ 978-0-387-49820-1

    work page 2008

  6. [6]

    Keogh, K

    E. Keogh, K. Chakrabarti, M. Pazzani, S. Mehrotra, Dimensionality re- duction for fast similarity search in large time series databases, Knowl- edge and Information Systems 3 (3) (2001) 263–286.doi:10.1007/ PL00011669

    work page 2001

  7. [7]

    J. Lin, E. Keogh, S. Lonardi, B. Chiu, A symbolic representation of time series, with implications for streaming algorithms, in: Proceedings of the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 2003, pp. 2–11.doi:10.1145/882082.882086

    work page doi:10.1145/882082.882086 2003

  8. [8]

    Frydrych, Modelowanie charakterystyk magnesowania amorficznych rdzeni dwuosiowych sensorów transduktorowych, Ph.D

    P. Frydrych, Modelowanie charakterystyk magnesowania amorficznych rdzeni dwuosiowych sensorów transduktorowych, Ph.D. thesis, Warsaw University of Technology (2019). 9 Algorithm 1Extremum Stack Update (wiping-out rule) Require:StackΠ, previous extremume prev, current directiond∈ {+1,−1,0}, new observationu Ensure:Updated(Π, e prev, d) 1:d new ←sign(u−e pr...

    work page 2019