CS Paper Radar

General constructions of normal bent partitions related to vectorial dual-bent functions

Alexander Kholosha, Mohit Pal

cs.DM math.CO ·submitted 2026-10-02 15:08 UTC · v1
theory

Abstract

Bent partitions were introduced as a generalization of partial spread construction of bent functions and they became a hot research topic recently. In this paper, we prove two general constructions of normal bent partitions that are related to vectorial dual-bent functions. They cover many of the currently known bent partitions of this type as partial cases. These constructions also provide a large number of new bent partitions. Relevant properties of bent functions obtained from such partitions are proven.

Closest papers

Nearest neighbours by meaning across the whole index.

Characterizations and MacWilliams-Like Identities of Weakly Regular Bent Partitions

cs.IT ·2026-10-30 ·Jiaxin Wang, Yadi Wei, Fang-Wei Fu, Jin Li, Fulin Li
theory similarity 0.71
Abstract

Bent partitions play a significant role in the theory of bent functions. In this paper, we study weakly regular bent partitions, that is, all generated bent functions are weakly regular (called in class $\mathcal{WRBP}$). Let $Γ=\{A_{i}, i \in V_{m}\}$ be a bent partition of $V_{n}$ in class $\mathcal{WRBP}$, where $V_{n}$ denotes an $n$-dimensional vector space over the prime field $\mathbb{F}_{p}$, $n$ is even, $m \leq \frac{n}{2}$, and $m \geq 2$ if $p=2$. We first characterize bent partition $Γ$ in terms of the duals of component functions of vectorial bent functions. In particular, we prove that if $p \neq 3$, then all bent functions generated by $Γ$ are regular. Building on the above result, we give characterizations of bent partition $Γ$ in terms of two classes of linear codes. When $n \geq 4$ and $m=\frac{n}{2}$, except for the case where $(p, n)=(2, 4)$ and $|A_{i_{0}}|=1$ for some $i_{0}$, we show that $Γ$ is obtained from a spread (after a shift). Particularly, any normal bent partition of $V_{n}$ of depth $p^{\frac{n}{2}}$ in class $\mathcal{WRBP}$ must be obtained from a spread (after a shift), where $n \geq 4$. We establish the Macwilliams-like identities for bent partitions in class $\mathcal{WRBP}$. Furthermore, if $p$ is odd, we present some nonexistence results on bent partitions in class $\mathcal{WRBP}$.

0.13

Generalized $p$-ary $\cPS$ Bent Functions

cs.IT cs.DM ·2026-09-16 ·Alexander Kholosha, Mohit Pal
similarity 0.62
Abstract

We use $m$-dimensional partial spreads of $\fp^{2n}$, where $p$ is an odd prime, $n$ is a positive integer and $m$ divides $n$, to construct two classes of bent functions from $\fp^{2n}$ to $\fp$. Our construction generalizes the classes of $p$-ary $\cPS^{-}$ and $\cPS^{+}$ bent functions proposed by P. Lison\v ek and H. Y. Lu (Des. Codes Cryptogr. 73 (2014), 209--216).

0.28

Bent Functions and the Completed Maiorana-McFarland Class

cs.IT math.HOmath.CO ·2026-08-20 ·Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin
surveyunusual similarity 0.60
Abstract

In this article, we survey some fundamental results and recent advances in the design and analysis of Boolean bent functions from the perspective of their relation to the completed Maiorana-McFarland class.

0.48

A counterexample to Tokareva's conjecture on sums of two bent functions

cs.IT math.CO ·2026-10-23 ·Yansong Feng, Hao Jiang, Guancheng Li, Tianyi Li, Lili Tang
similarity 0.51
Abstract · The counterexamples and proofs in this paper were obtained through large-scale automated reasoning with LLM agents while solving Problem~10 …

It is well known that the sum of two bent functions on $\mathbb{F}^n$ has algebraic degree at most $n/2$ for even $n\ge 4$. Tokareva conjectured that the converse holds: every Boolean function with degree at most $n/2$ can be written as a sum of two bent functions. The conjecture has been verified for even $n\leq 6$ and for several special classes of Boolean functions. We disprove this conjecture by showing that $x_1x_2(x_3x_4+x_5x_6+x_7x_8)$ is not a sum of two bent functions on $\mathbb{F}^8$. We extend this construction to obtain counterexamples in every even dimension $n\ge 8$. Using Shaporenko's reduction, we also obtain explicit counterexamples to Tokareva's derivative conjecture in every even dimension $n\ge 10$.

0.47

On different notions related to APN mappings

cs.IT math.CO ·2026-09-18 ·René Rodríguez-Aldama, Ajla Šehović, Enes Pasalic, Sadmir Kudin
similarity 0.51
Abstract · 30 pages, 2 figures, 3 tables. Example 3.2 has been added. As a consequence, Conjecture 3.1 was modified and renamed as Open Problem 1. The …

An APN mapping $F:\mathbb{F}_{2^n}\to \mathbb{F}_{2^n}$ is a polynomial characterized by the non-vanishing property on 2-flats. In this work, we analyze notions that are closely related to this property. To understand which $k$-flats of $\mathbb{F}_{2^n}$ remain flats under $F$, we study the $k$-breaking. The function $x^{-1}$ has been studied in the past in this context---we extend this study to general mappings and characterize the 2-breaking of APN functions. Recently, two generalizations of the APN property have been introduced: $k$-strongly non-normality and $k$-th-order sum-freedom. Sum-freedom generalizes the non-vanishing property of APN functions to higher dimensional flats. We provide in-depth observations of the relations between the breaking property, strongly non-normality and sum-freedom. We introduce a fourth concept called $k$-strongly breaking, which implies the breaking property. We derive several structural results for both notions and give a characterization of a subclass of APN functions in terms of the 2-strongly breaking property. We propose a different perspective of the non-vanishing property via a natural character transformation, which is closely related to the sum-of-square indicator of the components of $F$. We derive a precise value for the total sum of the sum-of-square indicators of $F$. With this approach, we provide a simple answer to Open Problem 4 in IEEE Trans. Inf. Theory 52(9): 4160-4170, 2006. Moreover, it allows us to explore balancedness properties of polynomials, one of which characterizes component-wise APNness, for odd $n$, and provides a natural extension to any dimension. We show that Dillon's APN permutation and the Gold functions satisfy a related property, termed $k$-balanced, which is presented under our framework.

0.34

Explicit Constructions of Maximum-Cardinality Families of Plateaued Functions with Pairwise Disjoint Walsh Supports

cs.IT ·2026-09-18 ·Chen Wang, Xiaoyan Zhang, Chunming Tang, Zhengchun Zhou
hot direction similarity 0.50
Abstract

Families of plateaued Boolean functions with pairwise disjoint Walsh supports are useful in secondary constructions of cryptographic Boolean functions. Of particular interest are maximum-cardinality families whose members admit no nonzero linear structures. To the best of our knowledge, the previously known general construction attaining both properties is spectral (Hodžić et al., IEEE Trans. Inf. Theory 65(9): 5865--5879, 2019). In that work, explicit algebraic normal forms are not generally provided, and no general method is established for prescribing a common algebraic degree for all family members. In this paper, we present two new explicit algebraic constructions within a unified framework, one based on linear functions and the other on partially linear functions with bent components. Let $p\geq 2$ and $q\geq 0$ satisfy $q<2^p-p-1$, and set $m=p+q$. Both constructions yield maximum-cardinality families of $2^{q+1}$ $(q+1)$-plateaued Boolean functions with pairwise disjoint Walsh supports. No member admits a nonzero linear structure, and every member has an explicit generalized Maiorana--McFarland representation. The first construction produces functions in $m+p+1$ variables and realizes any prescribed common algebraic degree $3\leq d\leq p+1$, provided that $q<\sum_{i=2}^{d-1}\binom{p}{i}$; its maximum attainable degree $p+1$ is optimal. The second construction produces functions in $n+p+1$ variables, where $n>m$ and $n-m$ is even, and realizes any prescribed common algebraic degree $3\leq d\leq p+(n-m)/2$, provided that $q<\sum_{i=2}^{\min\{d-1,p\}}\binom{p}{i}$; its maximum attainable degree $p+(n-m)/2$ is next-to-optimal.

0.34

A Comment on Local Hypercube Inequalities

cs.IT math-phhep-thmath.CO+1 ·2026-08-24 ·Keyou Zhuo, Tian-Shun Chen, Kilar Zhang
unusual similarity 0.50
Abstract · 10 pages

This comment gives dimension-independent analytic proofs of the local inequalities arising in the odd- and even-dimensional constructions of higher-dimensional partition charge functions. The prior works established these inequalities by exhaustive computation in low dimensions and tested them numerically in selected higher dimensions.

0.30

Multiway Partition is FPT for Connectivity Functions

cs.DM math.CO ·2026-08-11 ·Tony Huynh, Eun Jung Kim, Sang-il Oum, Roohani Sharma, Marek Sokołowski
theory similarity 0.45
Abstract · New title and strengthened main theorem that only needs posimodularity. Application to Hypergraph Multiway Partition is also added. 9 Pages,…

Let $E$ be a set of $n$ elements, $f\colon2^E\to\mathbb Z_{\ge0}$ be submodular, $t_1,\ldots,t_r\in E$ be distinct, and $k\in\mathbb N$. The Submodular Multiway Partition problem asks whether $E$ has a partition $(P_1,\ldots,P_r)$ with $t_i\in P_i$ for all $i$ and $\sum_i f(P_i)\le k$. We prove that this problem can be solved in $r^{O(k)}n^{O(1)}$ time whenever $f$ is posimodular. This covers monotone submodular functions, matroid rank functions, and nonnegative combinations of monotone and symmetric submodular functions. When $f$ is a connectivity function, we remove the dependence on the number of terminals and obtain a $k^{O(k)}n^{O(1)}$-time algorithm. The proof is entirely elementary, and is arguably the simplest proof that Edge Multiway Cut is fixed-parameter tractable. As a new consequence, our main result immediately implies that Hypergraph Multiway Partition is fixed-parameter tractable.

0.10