A counterexample to Kourovka Notebook Problem 16.45

Abstract

Let b(G) be the largest size of an inclusion-minimal base, over all permutation representations of a finite group G, with bases taken for the permutation image. Let μ′(G) be the largest size of an independent subset of G, not necessarily generating G. We construct an explicitly specified affine group of order 100920 for which b(G) = 3 < 4 = μ′(G). The upper bound covers faithful and nonfaithful actions and does not depend on enumerating the subgroups of the affine group. Exact, independently implemented Python and C++ verifiers certify the small matrix-group inputs and the explicit witnesses. The obstruction is a subgroup of order two that is central in the complement but not normal in the ambient affine group.

The idea in plain English

There are two ways to measure how much independent information a finite group can contain. One asks how many group elements can be chosen so that none can be generated from the others. The other looks at actions by permutations and asks how large a set of observed points can be when every observation is essential to distinguish the permutations.

Peter Cameron asked whether the largest possible values always agree. This paper gives an explicit group with an independent set of four elements, while every inclusion-minimal permutation base has at most three points, across all actions. It also constructs an action that attains three, so both values are exact.

The obstruction is a small subgroup that behaves differently inside the matrix part of the construction and inside the full affine group. It is central in the former but not normal in the latter. This realizes the precise normality obstruction in Cameron’s earlier formulation of the question.

The official Kourovka Notebook now records the negative answer, cites this Zenodo paper and reports confirmation by P. J. Cameron. The paper remains an unrefereed preprint; that recorded confirmation is distinct from journal publication.

The precise result

The group is G = F₂₉² ⋊ H, where H is generated over F₂₉ by A = [[0,28],[1,0]] and B = [[2,7],[12,28]]. This specifies the actual matrix action. H is isomorphic to SL₂(5), and |G| = 29² · 120 = 100920.

For this group, b_f(G) = b(G) = 3 and μ′(G) = 4. Here b_f uses faithful permutation actions, b allows all actions, and μ′ is the maximum size of an independent subset, whether or not it generates G.

Minimal means inclusion-minimal: every selected point is essential. For a possibly nonfaithful action, a base has pointwise stabilizer equal to the action kernel, or equivalently trivial stabilizer in the permutation image.

The paper gives an independent generating four-set and a faithful inclusion-minimal three-point base in a disjoint-union coset action. Structural subgroup and normal-subgroup arguments supply the upper bounds for every action.

The four omission subgroups of the independent set have a nonnormal intersection of order two. The corresponding Boolean meet-semilattice has rank four, but no rank-four realization can have normal bottom. This gives the negative answer to Problem 16.45.

Why the result holds

The complement H has a unique involution. Every even-order subgroup contains it, which sharply limits families of subgroups whose intersection is trivial, while the quotient H/{±I} supplies a larger base in a nonfaithful action.

Over F₂₉, a line stabilizer in H is cyclic of order dividing four. This bounds the faithful base invariant of every subgroup of G that does not contain the full translation subgroup.

A faithful irredundant intersection family must contain such a subgroup. Restricting the other members to it gives the upper bound of three. Every nontrivial normal subgroup of G contains the translation subgroup, so nonfaithful actions reduce to the already controlled complement.

Explicit matrix and translation elements give the independent four-set, and three explicit affine subgroups give the faithful three-point base. Their omission intersection is central only in the complement. Taking normal cores destroys the four-way irredundancy rather than converting it into a larger base.

Scope and limitations

The construction is not claimed to have the smallest possible group order. It does not classify all counterexamples or determine the largest possible gap between the invariants.

The result concerns inclusion-minimal bases maximized over all actions. It should not be described as a result only about transitive actions, minimum-size bases in one fixed action, or ordered irredundant bases.

Faithful and arbitrary actions must remain distinct. For the complement H itself, b_f(H) = 2 while b(H) = 3; omitting nonfaithful actions would change the problem.

The characteristic matters. The paper exhibits a related characteristic-11 construction with a faithful minimal base of size four, so the same conclusion is not established for every finite field.

Finite exact verifiers check the explicit matrix groups and witnesses. The upper bound for every subgroup and action of the full affine group relies on the structural proof, rather than exhaustive enumeration of its subgroup lattice.

The official notebook’s reported confirmation is evidence of external recognition, not a journal acceptance or proof-assistant certificate. This page does not claim an exhaustive priority search beyond the cited primary sources.

Status and AI use

The publication revision and verification were prepared with extensive OpenAI Codex assistance, including separate AI agents and exact Python/C++ checks. Those internal checks are distinct from the confirmation reported in the official notebook and from journal peer review.

Read the paper

Open PDF in a full window · Download the original from Zenodo

Collaborate on this result

I welcome substantive collaboration on placing the counterexample within the broader theory of permutation bases and subgroup lattices, checking the exposition and exact certificates, and preparing it for journal review. Expertise in finite groups or computational group theory would be particularly useful.

Authorship and responsibilities would be discussed in relation to the substantive contributions made.

Cite this paper

Alec Kriebel. (2026). A counterexample to Kourovka Notebook Problem 16.45 (Version 1.0.1) [Preprint]. Zenodo. https://doi.org/10.5281/zenodo.22929486

Download BibTeX

Background and prior work

• Kourovka Notebook, 21st edition, current Problem 16.45 entry: Printed page 105 states Cameron’s question and records its negative solution, citing Zenodo 22929486 and reporting confirmation by P. J. Cameron.
• Cameron, Some measures of finite groups related to permutation bases: Propositions 3.1–3.2 and Corollary 3.3 give the subgroup and Boolean-semilattice formulations and the inequality. The normality condition is already the identified obstacle.
• Cameron, Independence and bases: Theme and variations: Section 6 treats all permutation representations, including nonfaithful ones, and restates the equality question with notation b₂ and μ↑.
• Cameron, The symmetric group, 7: The author’s earlier exposition distinguishes minimal bases from ordered irredundant bases and explains the normal-bottom semilattice condition.