🔢 mathematics

Designs, linear codes, plateaued functions, and their interconnections

This paper investigates the profound interconnections between combinatorial designs, linear codes, and Boolean functions.

Original authors: Jong Yoon Hyun, Jieun Kwon, Jiaxin Wang, Yansheng Wu

Published 2026-05-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jong Yoon Hyun, Jieun Kwon, Jiaxin Wang, Yansheng Wu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master architect working with three very different types of building materials: Designs (blueprints for patterns), Codes (secret languages for sending messages), and Functions (mathematical recipes that turn inputs into outputs).

For a long time, mathematicians have known that these three materials are secretly related, like three different languages describing the same underlying city. This paper, written by Hyun, Kwon, Wang, and Wu, acts as a new translator and a master builder. It doesn't just show that these materials are connected; it builds new structures using them and solves two long-standing mysteries about how they fit together.

Here is a simple breakdown of what they did, using everyday analogies.

1. The Three Main Characters

To understand the paper, you need to know the three main characters:

Boolean Functions: Think of these as "magic recipes." You put in a list of 0s and 1s (like a switchboard), and the recipe spits out a single 0 or 1. Some recipes are very chaotic and hard to predict (called "bent" or "plateaued" functions), which makes them very useful for keeping secrets in cryptography.
Linear Codes: Think of these as "secret codes" or "error-correcting languages." They are used to send messages so that if a few letters get garbled in transit, the receiver can still figure out the original message.
Combinatorial Designs: Think of these as "perfectly balanced patterns." Imagine a tournament schedule where every pair of players meets exactly the same number of times, or a garden where every pair of flowers is surrounded by the same number of specific bushes.

2. The Big Discovery: A New "Triple" Rule

The authors introduced a new concept called the Triple Symmetric Difference Property (TSDP).

The Old Rule: Previously, mathematicians knew about a rule where if you took two blocks (groups) in a pattern and mixed them up, the result was either another block or the exact opposite of a block.
The New Rule (TSDP): The authors found a deeper rule. If you take three distinct blocks and mix them all together, the result is still either a block or the opposite of a block.
The Analogy: Imagine you have three different colored paints. If you mix any two, you get a predictable color. The authors discovered that if you mix three specific paints together, you still get a predictable color (either a standard paint or its negative). This property helps them identify and classify these patterns much more accurately.

3. Solving the "Twin" Mysteries

The paper solves two specific riddles (Open Problems 14.20 and 14.23) posed by previous researchers, Ding and Tang.

The Riddle: If you have two "magic recipes" (Boolean functions) that look different but are actually just variations of each other (mathematically equivalent), do they produce the same "secret code" and the same "pattern"?
The Answer: Yes. The authors proved that if the recipes are equivalent, the resulting codes and patterns are also equivalent. It's like saying: "If two chefs use the same recipe (just with different names for the ingredients), they will bake the exact same cake and write the exact same instruction manual."
Why it matters: This confirms that the connection between the recipe, the code, and the pattern is unbreakable. You can't change one without changing the others in a predictable way.

4. Building New, Non-Identical Twins

One of the most interesting parts of the paper is finding "twins" that look identical but aren't.

The Scenario: The authors built two new families of patterns (designs).
The Twist: These two families have the exact same statistics (same number of points, same number of blocks, same connections). If you just looked at the numbers, they would seem identical.
The Reality: However, they are non-isomorphic. This means if you tried to map one pattern onto the other, it wouldn't fit. They are like two houses that have the exact same square footage and number of windows, but the floor plans are completely different.
How they did it: They used specific types of "magic recipes" (plateaued functions) that had no "linear structures" (no predictable shortcuts). This allowed them to create these unique, non-identical twins.

5. The "Automorphism" Group: Who is the Boss?

The paper also asks: "Who is in charge of these patterns?"
In math, the "Automorphism Group" is the set of all the ways you can shuffle the pieces of a pattern (like rotating a puzzle or swapping colors) without breaking the pattern's rules.

The authors calculated exactly who these "bosses" are for their new patterns.
They found that for certain types of recipes, the "bosses" form a very specific, well-known mathematical group (related to symplectic groups), which helps mathematicians understand the symmetry and structure of these designs deeply.

Summary

In plain English, this paper is a bridge builder.

It connects recipes (functions), codes, and patterns (designs) more tightly than before.
It introduces a new "Triple Mixing Rule" (TSDP) to better classify these patterns.
It solves two mysteries by proving that equivalent recipes always lead to equivalent codes and patterns.
It discovers new patterns that look identical on paper but are structurally different in reality.
It figures out exactly how these patterns can be shuffled and rotated without breaking.

The authors didn't just describe the connections; they built new structures using these connections and provided the keys (automorphism groups) to understand how they work.

Technical Summary: Designs, Linear Codes, Plateaued Functions, and Their Interconnections

1. Problem Statement

This paper investigates the profound interconnections between combinatorial designs, linear codes, and Boolean functions, specifically focusing on plateaued functions (a generalization of bent functions). The research is motivated by two specific open problems posed by Ding and Tang in their monograph Designs from Linear Codes (2022):

Open Problem 1 (14.20): What is the relationship between the equivalence of two bent functions $f$ and $g$ and the equivalence of the binary linear codes $eCD_f$ and $eCD_g$ derived from them?
Open Problem 2 (14.23): What is the relationship between the equivalence of two bent functions $f$ and $g$ and the isomorphism of the designs supported by the codes $eCD_f$ and $eCD_g$ ?

While previous work (notably by Bending, Dempwolff, and Neumann) established these relationships for bent functions (0-plateaued functions), the extension to $r$ -plateaued functions (where $0 \le r < m$ ) remained an open area of inquiry. Additionally, the paper seeks to characterize the structural properties (such as the Triple Symmetric Difference Property) of designs derived from these generalized functions.

2. Methodology

The authors employ a combination of algebraic combinatorics, coding theory, and Boolean function analysis. Key methodological components include:

Generic Construction Framework: The paper establishes a general method to construct incidence structures (designs) from Boolean functions $f_b$ indexed by a set $B$ , where blocks are defined as the support sets $\{p \in P : f_b(p) = 1\}$ .
Walsh Transform Analysis: The authors utilize the Walsh transform $W_f$ and its support $S_f$ to characterize the parameters of the resulting designs. They leverage the properties of $r$ -plateaued functions, where $|W_f(a)| \in \{0, \pm 2^{(m+r)/2}\}$ .
Algebraic Characterization of Equivalence: The study investigates the equivalence of designs and codes by analyzing the automorphism groups and the linear spans of incidence matrices. They utilize the relationship between affine equivalence of functions and the equivalence of their associated codes.
Symmetric Difference Properties: The paper introduces and analyzes the Triple Symmetric Difference Property (TSDP) for arbitrary 2-designs, extending the known Symmetric Difference Property (SDP) of symmetric designs.
Rank Analysis: The 2-rank of incidence matrices is used to classify designs, particularly distinguishing between minimal rank designs and those with higher ranks.

3. Key Contributions and Results

A. New Concepts and Generalizations

Triple Symmetric Difference Property (TSDP): The authors define a TSDP design as one where the symmetric difference of any three distinct blocks is either a block or the complement of a block. They prove that addition designs derived from $r$ -plateaued functions (with no nonzero linear structure) satisfy TSDP but generally fail the Double Symmetric Difference Property (DSDP), yielding non-symmetric simple 2-designs.
Extension to $r$ -Plateaued Functions: The paper generalizes Bending's construction of addition designs from bent functions to $r$ -plateaued functions. It provides a new, simplified proof (Lemma 5) for the existence of these designs and characterizes simple 2-designs on $2^{m-r}$ points (Theorem 3).

B. Resolution of Open Problems

The paper provides a unified solution to Ding and Tang's Open Problems 1 and 2 by extending the results to $r$ -plateaued functions:

Theorem 4 & 5: The authors establish that for $r$ -plateaued functions with no nonzero linear structure, the equivalence of the functions is equivalent to the isomorphism of their addition designs and the equivalence of their associated linear codes.
Theorem 7: Specifically addressing bent functions, the paper proves that the affine equivalence of two bent functions $f$ $f$ and $g$ $g$ is equivalent to:
1. The isomorphism of the designs $D_f$ and $D_g$ (constructed via a specific quasi-symmetric design method).
2. The equivalence of the linear codes $eCD_f$ and $eCD_g$ .
3. The isomorphism of designs held by minimum and middle weight codewords.
  This effectively resolves Open Problems 1 and 2.

C. Automorphism Groups

The paper computes the automorphism groups for addition designs and their corresponding linear codes:

Theorem 8: It characterizes the automorphism group $\text{Aut}(AD_f)$ of an addition design derived from an $r$ -plateaued function $f$ as being isomorphic to the automorphism group of the function $f$ itself, defined via specific affine permutations.
Corollary 5: For quadratic bent functions and specific Maiorana-McFarland bent functions, the automorphism groups are shown to be isomorphic to the semi-direct product of the symplectic group and a vector space ( $Sp_m(\mathbb{F}_2) \rtimes \mathbb{F}_2^m$ ).

D. Non-Isomorphic Designs with Identical Parameters

The paper constructs new families of Boolean functions that produce 2-designs with parameters identical to known designs (such as the complement of a point-hyperplane design or TSDP designs) but are non-isomorphic to them.

Theorem 9 & 10: These theorems demonstrate that even when parameters and 2-ranks coincide, the underlying structural properties (such as the TSDP status of the translation design) can distinguish the designs. For instance, if the translation design derived from a bent function is not a TSDP design, the newly constructed design is non-isomorphic to the standard addition design.

4. Significance and Claims

The paper claims to significantly extend the theoretical framework connecting Boolean functions, linear codes, and combinatorial designs. Its primary significance lies in:

Generalization: Moving beyond bent functions to the broader class of $r$ -plateaued functions, thereby unifying the study of symmetric and non-symmetric designs under a single framework.
Resolution of Open Problems: Providing definitive answers to the equivalence questions posed by Ding and Tang regarding bent functions and their associated codes/designs.
Structural Insight: Introducing the TSDP as a unifying property for 2-designs and demonstrating that addition designs from plateaued functions possess this property even when they are not symmetric.
Automorphism Characterization: Extending previous results by Bending, Dempwolff, and Neumann by computing automorphism groups for a wider class of functions and their associated codes.

The authors conclude that the interconnections among these three fields offer rich opportunities for further research, particularly in classifying minimal rank designs and exploring the automorphism groups of specific bent functions. The work does not propose new experimental applications but rather deepens the theoretical understanding of the structural relationships in coding and design theory.