The coordinate-deletion conjecture for powerful sets

About 9 years old · traced to

Let S⊆F2nS\subseteq\mathbb{F}_2^n be a powerful set with 2n−12^{n-1} elements, where n≥2n\geq2. Deleting a coordinate means removing that coordinate from every vector; the resulting vectors are distinguishable when they form the set F2n−1\mathbb{F}_2^{n-1}.

Coordinate-deletion conjecture. If SS is a powerful set, then one can find a coordinate such that deleting this coordinate from all the elements of SS yields the set F2n−1\mathbb{F}_2^{n-1}, so that all the new vectors are distinguishable.

This conjecture concerns the structure of powerful sets of exactly half the size of the ambient binary cube. The supplied text gives no indication that the claim is resolved, so it remains open here.

References

Primary source

Graham E. Farr and Andrew Y. Z. Wang, “Powerful sets: a generalisation of binary matroids”, arXiv:1705.07437 (2017).

Progress summary

Refreshed
Open

No public resolution has appeared: the conjecture remains open, with only linear cases and cases in small dimensions known.

The claim is recorded as Conjecture 3.8 in a paper presented in December 2016 and published on arXiv in 2017. It asks whether every powerful set of half the binary cube has a coordinate whose deletion produces all possible shorter vectors.

Known results

  • Linear powerful sets: the conjecture holds, via the associated binary matroid's rank n−1n-1.
  • Nonlinear powerful sets: the conjecture was known to hold for n≤6n\le6.
  • The source gives no proof for general nn and no counterexample.

Current status (as of September 2026): the conjecture is open; it is known for linear powerful sets and for n≤6n\le6, with no published proof or counterexample for general nn.

Sources

Solutions 0

No solutions have been posted yet.