CS Paper Radar

An Algebraic Framework for Data Systems: Classification and Optimization of Algebraic Structures for Data Organization and Coding

Kendy Inoa

cs.IT math.RA ·submitted 2026-08-31 19:15 UTC · v2

Abstract

Modern data systems are commonly studied through computational and information-theoretic methods, while their algebraic properties remain largely unexplored. This paper introduces a mathematical framework for modelling data systems using algebraic codes over finite groups, organized by an \emph{axiom signature}: each algebraic axiom of the data domain is shown to be \emph{sufficient} for a specific coding-theoretic capability, and each implication is given its precise reading (MDS parameters do not require a field; quotients require normality, not commutativity). Three types of results are presented. Proved: a Gilbert-Varshamov existence bound over arbitrary finite groups, commutative or not; explicit direct-sum codes over the elementary divisors of any finite abelian group; that transactions preserving a validity predicate form a submonoid of the full transformation monoid, which is not a group; that schema-preserving transformations form a finite group whose orbits are counted by Burnside's lemma; and that the constraint-preserving bijections of a data system form a finite group whose orbits partition the valid configurations. Demonstrated: an explicit code construction over $\mathbb{F}_5$, with known codes over $\mathbb{Z}_4$ and $(2^U,\triangle)$ cited to situate the framework. Proposed: an encoding efficiency measure Ef and an optimization functional $Φ$ with tunable weights, both evaluated at declared coding instances. Weight-independent comparison holds under componentwise dominance; in general the weight simplex decomposes into polyhedral chambers on which the induced order is constant.

Comment
26 pages, 7 tables, 22 references. Presented as a poster at ICM 2026, Philadelphia, PA, USA. Revised: assumptions clarified, theorems corrected, Gilbert-Varshamov bound added; classifier gives sufficient conditions; ranking weight-independence withdrawn

Closest papers

Nearest neighbours by meaning across the whole index.

A Rig of Transformations

cs.PL ·2026-08-11 ·Emma Tye
similarity 0.63
Abstract

In high-level functional languages, the compiler often gives users little control over the runtime representation of data types. Yet how we model data structures at the program level can be different to how we want to represent them at the binary level, for efficiency or legacy reasons. Hence being able to describe data layouts and their transformations for data types is a useful and necessary part of programming, but difficult to do correctly, efficiently and ergonomically. We present a model of finite algebraic data types as a commutative rig (a ring without additive inverses), where the rig-equalities are modelled by isomorphisms between data. Using this approach, we can also model embedding a data type into a larger type (e.g. bit-padding) as a partial isomorphism.

0.04

Random Non-Commutative Error-Correcting Codes

cs.IT math.GR ·2026-10-28 ·Michael Best, Alexander Lubotzky
similarity 0.57
Abstract · 18 pages, 1 table

Chapman, Dinur, and Lubotzky recently introduced the theory of non-commutative error-correcting codes, generalizing classical coding theory to arbitrary groups via $δ$-robust subsets used to detect proper subgroups. Building on this foundation, this paper systematically studies an analogue of random codes for arbitrary groups, exploring the extent to which the classical Gilbert-Varshamov (GV) bound holds in this non-commutative setting. While random universal codes of linear size in free groups are shown to be asymptotically bad, we establish a complete characterization for general families of finite groups. Specifically, a family of finite groups admits good random codes (forming a GV family) if and only if it exhibits uniform polynomial maximal-subgroup growth. Furthermore, we provide explicit quantitative bounds on the rate and optimal distance range based on intrinsic parameters, proving that families of finite solvable groups always form GV families and determining the exact probabilistic rate for direct powers of a fixed finite simple group.

0.25

Foundations of Algebraic Architecture Theory: A Rising Sea of Geometry, Transport, Comparison, and Reconstruction

cs.SE cs.PL ·2026-09-23 ·Hiroyuki Nakahata
theory similarity 0.55
Abstract · 285 pages, 4 figures. Also archived on Zenodo with the same source: https://doi.org/10.5281/zenodo.22913488

AI-generated software changes make it increasingly important to determine what a change preserves, where local consistency fails to extend globally, and which alternatives remain. We develop the foundations of Algebraic Architecture Theory (AAT) from Atoms, typed primitive facts, and Laws, equations that objects must satisfy. A reading specifies what counts as structure and which operations and laws to preserve. The main reconstruction theorem identifies the category of full geometries and all their structure-preserving morphisms with an independently defined category of local models, up to equivalence. Objects are recovered up to isomorphism and morphisms between fixed endpoints uniquely. The theory addresses gluing, diagnosis, transport, classification of changes, and reconstruction. From finite Atom families we construct cores closed under operations and geometries with sites and coefficients. We give conditions under which a Cech obstruction detects the existence of a global state and, through comparison with repair semantics, a global repair. We compare diagnoses and give a finite criterion for uniform invariance given computable finite data. Transport along exact changes has a universal property and commutes with base change on exact pointed pullback squares. Comparisons of routes generated from the same square, finite comparison diagram, and geometry factor into an invertible comparison and an idempotent normalization. We characterize when observations determine comparison preservation and classify compatible lifts. Encodings of lens and protocol semantics preserve and reflect laws and recover semantics-preserving morphisms. Applications classify and count operation-preserving changes and extend morphisms uniquely from finite tables. Corresponding Lean declarations are listed in the appendix.

0.45

Mathematical foundations for symmetric programming and reasoning

cs.PL cs.LOmath.CTmath.GR+1 ·2026-11-12 ·Ohad Kammar, Matija Pretnar
similarity 0.55
Abstract

We develop a mathematical abstraction for uniformly exploiting symmetries in programming and reasoning based on the mathematical proof principle `without-loss-of-generality' (w.l.o.g.). Given: group actions that describe symmetries of the input and the output; and a canoniser, which captures how arbitrary inputs get sent to canonical ones, our construction extends any function from the canonical inputs to the whole domain. We characterise the conditions on the canonisers which guarantee that the construction gives the unique equivariant (i.e. symmetry-preserving) extension. Furthermore, we adapt the construction to a dependently-typed setting, where it captures traditional symmetric w.l.o.g. arguments via the Curry-Howard correspondence. Finally, we extend the construction to algebraic data types, where the symmetries of the constructors both uniquely determine the symmetries of the data type and pave the way for efficient execution.

0.30

Constructing Good Abelian Codes via Shift Bounds and Genetic Algorithms

cs.IT ·2026-08-19 ·Cong Yu, Hao Chen, Zhonghua Sun, Shixin Zhu
similarity 0.54
Abstract · 13 pages

This paper investigates the construction of linear codes via abelian codes over finite fields. By exploiting the algebraic structure of multivariate polynomial quotient rings, we derive lower bounds on the minimum distance using a generalized shift bound, which extends the classical van Lint-Wilson bound for cyclic codes. Several infinite families of abelian codes are explicitly constructed, including binary and ternary cases that extend previously known cyclic constructions. To find more abelian codes with good parameters, we apply a genetic algorithm that searches over defining sets represented as binary chromosomes of cyclotomic cosets; the fitness function compares the computed minimum distance against the best known linear code (BKLC) bounds. The search yields multiple record-breaking codes over F_3 and F_4, with improvements over Grassl's tables. Furthermore, the nested structure of these codes enables the application of Construction X, yielding additional linear codes with improved parameters. The results demonstrate that abelian codes, combined with heuristic search, form a viable way for discovering linear codes with unknown parameters.

0.28

Subgroup Accessibility in Group Order Logic

cs.LO cs.CCmath.LO ·2026-08-31 ·Anatole Dahan
theory similarity 0.54
Abstract

We investigate the expressive power of fixed-point logics (FP) and their extensions in defining generating sets for accessible subgroups of definable permutation groups. This operation, computable in polynomial time via the Schreier-Sims algorithm, plays a central role in the group-theoretic approach to Graph Isomorphism and Graph Canonisation. In particular, it underpins polynomial-time canonisation for bounded colour-class graphs--a class for which no natural logic capturing P is currently known. We first show that this operation cannot, in general, be expressed in any logic for P. This limitation arises from the fact that accessible subgroups need not admit symmetric generating sets of polynomial size. However, we prove that when the base group admits a definable ordered generating set, the accessible subgroup operation becomes definable in fixed-point logic with the group order operator (FP + ord). This is achieved by partially simulating the Schreier-Sims algorithm within FP + ord. As a corollary, we show that fixed-point logic with counting (FPC) can also define the operation when the base group is abelian. In particular, FPC can define the automorphism group of any graph with abelian colours--despite being unable to canonise such graphs.

0.21

Scenes: A Meta-Logical Algebra for Mutable State

cs.LO ·2026-09-24 ·Simon Foster, Carlos Isasa, Christian Pardillo Laursen
hot direction similarity 0.54
Abstract · Submitted to MFCS 2026, rejected. Plan to revise and resubmit elsewhere

Modelling of mutable state spaces and precisely describing how variables are manipulated in a program is a fundamental problem in compositional verification. Though we can make use of the embedded abstract syntax of a program for such analysis, this runs contrary to the shallow-embedding approach, and hampers efficient proof automation. On the other hand, lenses and prisms provide an elegant algebraic foundation for modelling state, which provide sufficient structure to provide meta-logical program analysis, but without requiring a deep embedding. Nevertheless lenses, as complex algebraic objects, cannot easily be combined, complemented, or collected in sets. In this paper we contribute an accompanying algebraic structure called the scene, which allows us to characterise the set of variables, or coordinates, in a state space. Scenes intuitively correspond to sets of lenses, but like lenses they are purely semantic algebraic objects. We demonstrate that scenes provide us with sufficient structure to characterise the lens-based meta-logical properties, like independence and equivalence. Moreover, we introduce the notion of a scene space, analogous to a vector space, which allows us to recover a set-like algebraic structure. Finally, we show how scenes allow us to characterise the free and bound variables of expressions and programs, without any need for syntax, and demonstrate their use for reasoning about programs by deriving reasoning principles for the parallel composition operator.

0.34

Constructions of reversible linear and DNA codes through $T_{D,g}^n-$set and $(n_1,c_1|n_2,c_2)-$right polycyclic codes

cs.IT math.RA ·2026-11-17 ·Avanish Kumar Chaturvedi, Satyadeep Pandey
similarity 0.54
Abstract

In this paper we give a construction technique of $T_{D,g}^n-$set for reversible linear codes and reversible DNA codes with their code parameters. This technique yields many reversible MDS codes which significantly improves the $T^n-$set construction by Oztas et.al. in terms of obtained code parameters. Concatenation-based constructions are presented for reversible linear codes satisfying self-duality and linear complementary dual (LCD) conditions, giving necessary and sufficient condition for desired dual properties. We introduce a new notion of $(n_1,c_1|n_2,c_2)-$ right polycyclic codes. Also, a new construction technique is developed to obtain reversible linear $(n_1,c_1|n_2,c_2)-$ right polycyclic codes with good parameters (MDS codes) over any finite commutative rings.

0.29