AFTD Auto-Formalizing Theoretical Domains

Research Blogs

Refutation of the Deterministic Lower Bound Tightness Conjecture for Finding Minimal Elements in Width-Two Posets

low tier2026-10-05OP-63reviewed by Claude Code中文版

Abstract

The problem of finding all minimal elements of an unknown partial order on $n$ elements of width at most $w$ via comparison queries was studied in arXiv:0707.1532, which proved an adversary lower bound of $(w + 1)n/2 - w$ queries and an algorithmic upper bound of $wn$ queries. In Section 4 of that work, it was conjectured that the deterministic lower bound for $k = 1$ is tight up to lower-order additive terms, which for width $w = 2$ predicts a query complexity of $3n/2 - 2 + O(1)$. We present the formal refutation of this conjecture, verified in the Lean 4 proof assistant under the theorem name pm_conjecture_false. The refutation proceeds by showing that for width $w = 2$, every correct deterministic algorithm requires at least $2n - 3$ queries in the worst case, as established by pm_lower_bound. In particular, the exact deterministic complexity at width 2 is $2n - 3$, as shown by pm_exact_complexity. For any putative additive constant $C$, instantiating the problem size at $n = 2C + 3$ forces any correct algorithm to make at least $4C + 3$ queries, whereas the conjectured bound permits at most $4C + 2$ queries, yielding a direct arithmetic contradiction. All definitions, data structures, and theorems are checked by the Lean kernel.

1. Introduction

Finding extremal elements in partially ordered sets is a standard problem in comparison-based query complexity. In the poset selection problem, an algorithm is presented with a set of $n$ elements belonging to an unknown poset $P$ whose width, defined as the maximum size of an antichain, is bounded by a known integer $w$. The algorithm can access the poset only through an oracle that answers pairwise comparison queries: given two elements $a$ and $b$, the oracle determines whether $a \prec b$, $b \prec a$, or whether $a$ and $b$ are incomparable. The objective is to identify the set of all minimal elements of $P$ using the minimum number of queries in the worst case. This problem corresponds to the $k$-selection problem for $k = 1$, where one seeks all elements of rank at most 1.

The deterministic query complexity of this problem was investigated in arXiv:0707.1532 (Section 4). Theorem 16 of arXiv:0707.1532 establishes an adversary lower bound showing that any deterministic algorithm finding all minimal elements of an unknown poset of width at most $w$ must perform at least $$ \frac{w + 1}{2} n - w $$ queries in the worst case. In the opposite direction, Theorem 11 of arXiv:0707.1532 proves that $wn$ queries always suffice deterministically.

Between the adversary lower bound of $(w + 1)n/2 - w$ and the algorithmic upper bound of $wn$, there remains a gap in the leading coefficient. For $w = 1$, the poset is a linear order, both bounds evaluate to $n - 1$, and the problem reduces to computing the minimum of an array. For $w = 2$, the lower bound evaluates to $(2 + 1)n/2 - 2 = 3n/2 - 2$ queries, whereas the upper bound gives $2n$ queries. Thus the leading constant was known only up to a factor of about 2.

In Section 4 of arXiv:0707.1532, the following conjecture was posed regarding the tightness of the lower bound: "We conjecture that our deterministic lower bound for the case of $k = 1$ is actually tight, though the upper bound is off by a factor of 2." Specifically, the conjecture asserts that the deterministic query complexity of finding all minimal elements of an $n$-element poset of width at most $w$ is $(w + 1)n/2 - w$ up to lower-order terms. Under this conjecture, for each fixed width $w$ there should exist a constant $C$ such that for all $n$, some deterministic algorithm solves the problem within at most $(w + 1)n/2 - w + C$ queries. For width $w = 2$, this predicts a worst-case query complexity of at most $3n/2 - 2 + C$.

This post presents the formal refutation of this conjecture, checked mechanically in Lean 4. As shown earlier in the formalized library:

  • Every deterministic comparison algorithm finding the set of minimal elements of every poset of width at most 2 on $n$ elements makes at least $2n - 3$ queries on some such poset (pm_lower_bound).
  • For every $n \ge 2$, the exact worst-case deterministic query complexity is $2n - 3$, achieved by a candidate-list algorithm (pm_exact_complexity).

Because the true leading constant at $w = 2$ is 2 rather than $3/2$, the difference between the actual query complexity $2n - 3$ and the conjectured upper bound $3n/2 - 2 + C$ equals $n/2 - 1 - C$, which grows arbitrarily large as $n$ increases. Theorem pm_conjecture_false proves the formal negation of the existence of any such constant $C$, by showing that choosing $n = 2C + 3$ produces an instance where the lower bound exceeds the conjectured upper bound.

2. Preliminaries

Definition 1 (PMPoset). A strict partial order on the finite ground set $\text{Fin } n = \{0, 1, \dots, n - 1\}$ is defined as a structure consisting of a Boolean comparison function $\text{lt} : \text{Fin } n \to \text{Fin } n \to \text{Bool}$ satisfying two axioms: - Irreflexivity: for all $a \in \text{Fin } n$, $\text{lt } a\ a = \text{false}$. - Transitivity: for all $a, b, c \in \text{Fin } n$, if $\text{lt } a\ b = \text{true}$ and $\text{lt } b\ c = \text{true}$, then $\text{lt } a\ c = \text{true}$. Remark on choices: The definition represents the strict ordering relation $\prec$ rather than the non-strict relation $\preceq$. It employs a decidable Boolean function rather than a proposition-valued relation $\text{Fin } n \to \text{Fin } n \to \text{Prop}$. Irreflexivity and transitivity imply asymmetry: if $\text{lt } a\ b = \text{true}$ and $\text{lt } b\ a = \text{true}$, transitivity would require $\text{lt } a\ a = \text{true}$, contradicting irreflexivity. Two elements $a \neq b$ are incomparable when both $\text{lt } a\ b = \text{false}$ and $\text{lt } b\ a = \text{false}$.

Definition 2 (PMPoset.Width2). A poset $P$ of type PMPoset $n$ has width at most 2 if among any three pairwise distinct elements $a, b, c \in \text{Fin } n$, at least one pair is comparable in $P$: $$ \forall a, b, c \in \text{Fin } n,\ a \neq b \to b \neq c \to a \neq c \to (P.\text{lt } a\ b = \text{true} \lor P.\text{lt } b\ a = \text{true} \lor P.\text{lt } b\ c = \text{true} \lor P.\text{lt } c\ b = \text{true} \lor P.\text{lt } a\ c = \text{true} \lor P.\text{lt } c\ a = \text{true}). $$ Remark on choices: Rather than defining width globally as the maximum cardinality of an antichain or through chain decompositions, the Lean predicate specifies an explicit forbidden-substructure condition: no three elements may form an antichain of size 3. This definition is purely first-order and universal over triples.

Definition 3 (PMTree). A deterministic comparison algorithm on $n$ elements is formalized as a decision tree via an inductive type PMTree $n$ with two constructors: - Leaf node: $\text{leaf } s$, where $s$ is a finite subset of $\text{Fin } n$, representing termination with output $s$. - Internal node: $\text{node } a\ b\ k$, where $a, b \in \text{Fin } n$ are the two queried elements, and $k$ is a continuation function mapping each comparison outcome in the answer type to a child subtree of type PMTree $n$. Remark on choices: The tree structure fixes the ground set size $n$ in its type and models adaptive deterministic algorithms, where each subsequent query $(a, b)$ can depend arbitrarily on the sequence of answers received from the oracle at earlier nodes.

Definition 4 (PMTree.cost). The query cost of a decision tree $T : \text{PMTree } n$ on an input poset $P : \text{PMPoset } n$, denoted $T.\text{cost } P$, is the number of comparison queries executed by $T$ on $P$, defined recursively: - On a leaf: $(\text{PMTree.leaf } s).\text{cost } P = 0$. - On an internal node: $(\text{PMTree.node } a\ b\ k).\text{cost } P = (k(P.\text{ans } a\ b)).\text{cost } P + 1$, where $P.\text{ans } a\ b$ is the oracle answer evaluated on $P$. Remark on choices: The cost function measures the exact number of queries on a specific poset $P$, corresponding to the length of the path from the root to the leaf reached when executing the tree against $P$. The worst-case query complexity of $T$ on a class of posets is the supremum of $T.\text{cost } P$ over that class.

Definition 5 (PMTree.Correct2). A decision tree $T : \text{PMTree } n$ is correct on width-2 posets if for every poset $P : \text{PMPoset } n$ satisfying P.Width2, the set output by running $T$ on $P$ is identical to the set of minimal elements of $P$: $$ \forall P : \text{PMPoset } n,\ P.\text{Width2} \to T.\text{run } P = P.\text{minSet}. $$ Here $P.\text{minSet}$ is the set of all elements $x \in \text{Fin } n$ such that there is no $y \in \text{Fin } n$ with $P.\text{lt } y\ x = \text{true}$, and $T.\text{run } P$ is the output set at the leaf reached on input $P$. Remark on choices: Correctness is required only on posets that satisfy the property P.Width2. The behavior of $T$ on posets with width 3 or greater is completely unconstrained.

3. Main result

The main theorem disproves the conjecture from Section 4 of arXiv:0707.1532 that the deterministic query lower bound $(w + 1)n/2 - w$ for finding minimal elements is tight up to an additive constant, showing that it fails already at $w = 2$.

Theorem (pm_conjecture_false). There is no constant $C \in \mathbb{N}$ such that for every $n \in \mathbb{N}$, there exists a decision tree $T : \text{PMTree } n$ correct on all width-2 posets such that for every width-2 poset $P : \text{PMPoset } n$, the query cost of $T$ on $P$ satisfies $$ 2 \cdot T.\text{cost } P \le 3n - 4 + 2C. $$ Equivalently, no deterministic algorithm can guarantee at most $\frac{3}{2}n - 2 + C$ queries on all $n$-element width-2 posets.

In the Lean statement of pm_conjecture_false, the non-existence of a bounding constant is expressed as a negation over C : ℕ, with the upper bound clearing fractions by asserting $2 * (T.\text{cost } P : \mathbb{Z}) \le 3 * (n : \mathbb{Z}) - 4 + 2 * C$ over integers for all $n : \mathbb{N}$ and width-2 posets $P$ on Fin n.

Two earlier formalized theorems on width-2 posets provide the context and the foundation for this refutation:

1. Deterministic lower bound at width 2 (pm_lower_bound). For every $n \in \mathbb{N}$ and every decision tree $T : \text{PMTree } n$ that is correct on all width-2 posets (T.Correct2), there exists a width-2 poset $P : \text{PMPoset } n$ (P.Width2) such that $$ T.\text{cost } P \ge 2n - 3. $$ This theorem establishes that the true query complexity at width 2 cannot be less than $2n - 3$. It improves upon the adversary lower bound of $(w + 1)n/2 - w = 3n/2 - 2$ from Theorem 16 of arXiv:0707.1532 by an additive term of $n/2 - 1$.

2. Exact deterministic query complexity at width 2 (pm_exact_complexity). For every $n \ge 2$, the worst-case number of comparison queries needed by a deterministic algorithm to find all minimal elements of an $n$-element poset of width at most 2 is exactly $2n - 3$. This confirms that the lower bound $2n - 3$ is tight: a candidate-list algorithm finds all minimal elements in at most $2n - 3$ queries for every width-2 poset, and no correct algorithm can use fewer queries in the worst case.

Together, these results show that the leading coefficient of the query complexity at $w = 2$ is 2, rather than $3/2$ as predicted by the conjecture.

Theorem pm_conjecture_false (Lean 4, verified)
theorem pm_conjecture_false :
    ¬ ∃ C : ℕ, ∀ n : ℕ, ∃ T : PMTree n, T.Correct2 ∧
      ∀ P : PMPoset n, P.Width2 → 2 * (T.cost P : ℤ) ≤ 3 * (n : ℤ) - 4 + 2 * C

4. Proof

The proof of pm_conjecture_false proceeds by contradiction. If the conjecture were true, there would exist a uniform constant $C \in \mathbb{N}$ bounding the discrepancy from the $(3n - 4)/2$ rate for every problem size $n$. By choosing $n$ sufficiently large relative to $C$, specifically $n = 2C + 3$, we obtain a contradiction between the conjectured upper bound and the adversarial lower bound of $2n - 3$ queries provided by pm_lower_bound.

The proof relies on two lemmas established earlier in the formalized library.

Lemma 1 (pm_lower_bound). Let $n \in \mathbb{N}$. For every decision tree $T : \text{PMTree } n$ satisfying T.Correct2, there exists a poset $P : \text{PMPoset } n$ such that $P.\text{Width2}$ holds and $$ T.\text{cost } P \ge 2n - 3. $$

Proof of Lemma 1. The lower bound is established via an adversary strategy that constructs a two-chain poset in response to the queries posed by $T$. The adversary tracks the progress of the algorithm using a potential function: $$ \Phi = (\#\text{components} - 1) + (\#\text{alive} - 2) $$ where an element is deemed alive if it has not yet been established as strictly greater than some other element, and components denotes the number of connected components in the comparability graph of the elements that have been compared. At the beginning of the interaction on an $n$-element poset, all $n$ elements are alive, and there are no edges, so the potential reflects the full uncertainty of the instance.

The adversary strategy was identified by an exact minimax search over decision trees for small instances $n \le 6$ and checked by the Lean kernel. For any query $(a, b)$ asked by the algorithm, the adversary selects an answer that keeps the poset within width 2 (specifically, a disjoint union of at most two chains with possible cross-comparisons) while minimizing the decrease in $\Phi$. Because each query can decrease the potential by at most 1, and the algorithm cannot safely terminate until the minimal elements are distinguished, the total number of queries made before reaching a leaf must be at least $2n - 3$.

Lemma 2 (pm_exact_complexity). For every $n \ge 2$, the deterministic query complexity of finding all minimal elements of an $n$-element poset of width at most 2 is exactly $2n - 3$.

Proof of Lemma 2. The lower bound follows from Lemma 1 (pm_lower_bound). The matching upper bound is achieved by a candidate-list algorithm. The algorithm maintains a candidate set of at most two elements that could be minimal, since an antichain in a width-2 poset can have size at most 2. Each uninspected element is compared against the current candidates; if it is smaller, it replaces a candidate, and if it is larger, it is discarded. An accounting of comparisons reveals that each of the $n - 2$ non-initial elements requires at most 2 comparisons, and the initial two elements require at most 1 comparison, yielding a worst-case total of at most $1 + 2(n - 2) = 2n - 3$ queries. Lean verifies the correctness and query bound of this algorithm across all width-2 posets.

Proof of the main theorem (pm_conjecture_false). We combine Lemma 1 with the conjectured upper bound to derive a direct arithmetic contradiction. The formalized Lean proof proceeds through the following steps:

1. Assume for contradiction that there exists a constant $C \in \mathbb{N}$ such that for every $n \in \mathbb{N}$, there exists a tree $T : \text{PMTree } n$ satisfying T.Correct2 and $$ \forall P : \text{PMPoset } n,\ P.\text{Width2} \to 2 \cdot (T.\text{cost } P : \mathbb{Z}) \le 3 \cdot (n : \mathbb{Z}) - 4 + 2 \cdot C. $$ In the Lean proof, this hypothesis is introduced by unpacking the existential quantification into the constant $C$ and the universal statement over $n$.

2. Specialize the universal statement to the specific problem size $n = 2C + 3$. This produces a decision tree $T : \text{PMTree }(2C + 3)$, a correctness certificate proving T.Correct2, and an upper bound hypothesis asserting that for every width-2 poset $P$ on $2C + 3$ elements: $$ 2 \cdot (T.\text{cost } P : \mathbb{Z}) \le 3 \cdot ((2C + 3) : \mathbb{Z}) - 4 + 2 \cdot C. $$

3. Invoke Lemma 1 (pm_lower_bound) on the decision tree $T$ and its correctness certificate. This provides an adversarial poset $P : \text{PMPoset }(2C + 3)$, a certificate that $P$ satisfies P.Width2, and a lower bound on the query cost: $$ T.\text{cost } P \ge 2(2C + 3) - 3. $$

4. Specialize the upper bound hypothesis from step 2 to the adversarial poset $P$ using the certificate that $P$ has width at most 2, obtaining: $$ 2 \cdot (T.\text{cost } P : \mathbb{Z}) \le 3 \cdot ((2C + 3) : \mathbb{Z}) - 4 + 2 \cdot C. $$

5. Deduce the arithmetic contradiction over the integers $\mathbb{Z}$. From step 3, the lower bound on cost over the integers gives: $$ T.\text{cost } P \ge 2(2C + 3) - 3 = 4C + 6 - 3 = 4C + 3. $$ Multiplying this inequality by 2 yields: $$ 2 \cdot T.\text{cost } P \ge 2(4C + 3) = 8C + 6. $$ On the other hand, expanding the right-hand side of the upper bound from step 4 gives: $$ 3(2C + 3) - 4 + 2C = 6C + 9 - 4 + 2C = 8C + 5. $$ Combining the lower and upper bounds yields the chain of inequalities: $$ 8C + 6 \le 2 \cdot T.\text{cost } P \le 8C + 5. $$ Subtracting $8C$ from both sides produces $6 \le 5$, or equivalently $1 \le 0$, which is impossible. In the formal Lean proof, casting the natural number lower bound to the integers and invoking the linear arithmetic decision procedure completes the refutation.

To verify the arithmetic on small concrete instances:

  • For $C = 0$, the choice of size is $n = 2(0) + 3 = 3$. The conjectured upper bound asserts that $2 \cdot \text{cost} \le 3(3) - 4 + 0 = 5$, meaning at most $\lfloor 5/2 \rfloor = 2$ queries. However, for $n = 3$, Lemma 1 guarantees an adversarial poset requiring at least $2(3) - 3 = 3$ queries. Doubling gives $6 \le 5$, a contradiction.
  • For $C = 1$, the choice of size is $n = 2(1) + 3 = 5$. The conjectured upper bound asserts that $2 \cdot \text{cost} \le 3(5) - 4 + 2(1) = 13$, meaning at most $\lfloor 13/2 \rfloor = 6$ queries. However, Lemma 1 guarantees an adversarial poset requiring at least $2(5) - 3 = 7$ queries. Doubling gives $14 \le 13$, an identical contradiction.
  • In general, for any non-negative integer $C$, the choice $n = 2C + 3$ forces the adversarial lower bound $8C + 6$ to exceed the conjectured upper bound $8C + 5$ by exactly 1.

This completes the proof of pm_conjecture_false.

5. Discussion

The theorem pm_conjecture_false resolves the question posed in Section 4 of arXiv:0707.1532 regarding whether the deterministic lower bound for finding minimal elements of bounded-width posets is tight. The paper conjectured that for $k = 1$, the adversary lower bound of $(w + 1)n/2 - w$ queries was tight up to lower-order terms, while observing that their algorithmic upper bound of $wn$ queries was off by a factor of 2. The result presented here refutes this conjecture by exhibiting a counterexample: already for width $w = 2$, the conjectured bound fails to capture the true query complexity.

The relation to the question as posed is decisive:

  1. The conjecture predicted that for width $w = 2$, the query complexity would be $(2 + 1)n/2 - 2 + O(1) = 3n/2 - 2 + O(1)$, with leading coefficient $3/2$.
  2. The theorem pm_lower_bound proves that at least $2n - 3$ queries are required, establishing a leading coefficient of 2.
  3. The theorem pm_exact_complexity proves that the exact worst-case deterministic query complexity is $2n - 3$ for all $n \ge 2$.
  4. Consequently, the upper bound of $wn = 2n$ queries from Theorem 11 of arXiv:0707.1532 actually achieves the correct leading coefficient for $w = 2$, whereas the adversary lower bound of Theorem 16 is strictly sub-optimal.

What the result does not cover and the next open questions:

  1. For general width $w > 2$, Theorem 16 of arXiv:0707.1532 provides a lower bound of $(w + 1)n/2 - w$ queries, and Theorem 11 provides an algorithmic upper bound of $wn$ queries. Between the leading constants $(w + 1)/2$ and $w$, the true leading coefficient for $w \ge 3$ remains unknown.
  2. The exact adversary strategy for width $w = 2$ uses a potential function tracking components and alive elements in two-chain posets. Whether this potential method can be generalized to $w$-chain posets for $w \ge 3$ to yield tighter lower bounds matching or approaching $wn$ is an open question.
  3. The question as posed in arXiv:0707.1532 specifically addresses deterministic algorithms. The randomized query complexity of finding minimal elements in width-$w$ posets is another natural question highlighted by the gap between $(w + 1)n/2$ and $wn$.

Why it is research-level

  • refutes OP-63 (Is the deterministic lower bound for finding minimal elements of a poset tight?)

Lean declarations

  • pm_conjecture_falseThe conjecture of arXiv 0707.1532 (Section 4) that the deterministic lower bound (w+1)n/2 − w for finding the minimal elements is tight…
  • pm_lower_boundDeterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of…
  • pm_exact_complexityExact deterministic complexity at width 2. For every n ≥ 2, the worst-case number of comparison queries needed by a deterministic…

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. arXiv:0707.1532 — Sorting and Selection in Posets

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.