arxiv: 2604.17342 · v1 · submitted 2026-04-19 · 💻 cs.NE · cs.CR

Recognition: unknown

Monotone but Exciting: On Evolving Monotone Boolean Functions with High Nonlinearity

Claude Carlet, Domagoj Jakobovic, Luca Mariot, Marko {\DH}urasevic, Marko \v{C}upi\'c, Stjepan Picek

Authors on Pith no claims yet

Pith reviewed 2026-05-10 05:23 UTC · model grok-4.3

classification 💻 cs.NE cs.CR

keywords monotone Boolean functionsnonlinearityevolutionary algorithmsgenetic programmingtruth table encodingBoolean function optimization

0 comments

The pith

Evolutionary search can discover monotone Boolean functions with nonlinearities exceeding those of majority functions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper explores whether evolutionary computation can produce monotone Boolean functions with higher nonlinearity than is typical for this restricted class. The authors apply three different encodings for candidate functions and add a penalty term to the fitness function to enforce monotonicity. Experiments cover dimensions from 5 to 14 and compare results against the majority function and known upper bounds. In several cases the evolved functions improve on the majority function and approach the best recorded nonlinearity values for monotone functions. The work also documents clear differences in how well each encoding scales with dimension.

Core claim

By combining evolutionary algorithms with a non-monotonicity penalty in the fitness function, it is possible to evolve monotone Boolean functions whose nonlinearity surpasses that of the majority function for several dimensions between 5 and 14, and in some cases approaches the highest known values for monotone functions.

What carries the argument

A fitness function that adds a non-monotonicity penalty to objectives for nonlinearity and balancedness, applied across truth-table and genetic-programming encodings within an evolutionary search process.

If this is right

Monotone Boolean functions can achieve nonlinearities higher than those produced by the majority function.
The standard truth-table encoding remains competitive through dimension 14.
Genetic programming encodings become especially effective for the largest dimensions tested.
Balanced truth-table encodings degrade sharply as dimension increases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same penalty technique could be tested on other constrained Boolean-function properties such as resilience or correlation immunity.
Hybrid encodings that combine truth tables with tree representations might improve results at still higher dimensions.
If the method continues to scale, it may supply concrete examples useful for studying the gap between algebraic constructions and search-based constructions of monotone functions.

Load-bearing premise

The non-monotonicity penalty term reliably steers the search toward truly monotone functions without excluding high-nonlinearity candidates or introducing bias in the reported comparisons.

What would settle it

Direct verification that each reported function is monotone (no input flip from 0 to 1 decreases the output) together with exact nonlinearity computation for the best functions at n=10 or n=12 would confirm or refute the claimed improvements.

Figures

Figures reproduced from arXiv: 2604.17342 by Claude Carlet, Domagoj Jakobovic, Luca Mariot, Marko {\DH}urasevic, Marko \v{C}upi\'c, Stjepan Picek.

**Figure 1.** Figure 1: Non-monotone penalty variants. framework1 [11] and the code is available upon request. 5 Experimental Results In the experiments, we carry out experiments in two scenarios: optimization of balanced functions, with a single fitness function, and imbalanced Boolean functions with three fitness variants. Experiments are made using three encodings (TT, TTw, and GP) and problem sizes from 5 to 14 variables. As … view at source ↗

**Figure 2.** Figure 2: Results for n = 8 ● ● ● ● ● ● ● ● 50 100 150 200 n = 9, balanced fitness value TT TTw GP + + + ● ● ● 175 180 185 190 195 200 n = 9, imbalanced fitness value TT_fit1 TT_fit2 TT_fit3 GP_fit1 GP_fit2 GP_fit3 + + + + + + [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗

**Figure 3.** Figure 3: Results for n = 9 the plot for the balanced case in 13 variables is not shown (since the majority of TT results are negative). Furthermore, in n = 14 variables, the TT encoding does not succeed in finding a single monotone Boolean function, whether balanced or not; therefore, the plot for this case ( [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗

**Figure 4.** Figure 4: Results for n = 10 ● 550 600 650 700 750 n = 11, balanced fitness value TT GP + + ● ● ● ● 700 720 740 760 780 800 n = 11, imbalanced fitness value TT_fit1 TT_fit2 TT_fit3 GP_fit1 GP_fit2 GP_fit3 + + + + + + [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗

**Figure 5.** Figure 5: Results for n = 11 ● ● ● 1100 1200 1300 1400 1500 1600 n = 12, balanced fitness value TT GP + + ● ● ● 1350 1400 1450 1500 1550 1600 1650 n = 12, imbalanced fitness value TT_fit1 TT_fit2 TT_fit3 GP_fit1 GP_fit2 GP_fit3 + + + + + + [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗

**Figure 6.** Figure 6: Results for n = 12 13 [PITH_FULL_IMAGE:figures/full_fig_p013_6.png] view at source ↗

**Figure 7.** Figure 7: Results for n = 13 and n = 14, imbalanced functions 6 Conclusions and Future Work In this work, we studied the problem of evolving monotone Boolean functions with high nonlinearity. Unlike the classical setting of unrestricted Boolean-function design, monotone Boolean functions are subject to strong structural constraints, which significantly limit the achievable nonlinearity. This makes them an interesti… view at source ↗

read the original abstract

Monotone Boolean functions are a structurally important class of Boolean functions, but their restricted form imposes strong limitations on achievable nonlinearity. In this paper, we investigate whether evolutionary computation can evolve monotone Boolean functions with high nonlinearity, both in the balanced and imbalanced settings. We consider three solution encodings: the standard truth table representation, a balanced truth table encoding that preserves Hamming weight, and a symbolic tree-based genetic programming representation. To guide the search toward monotone increasing functions, we introduce a non-monotonicity penalty and combine it with fitness functions targeting balancedness and nonlinearity. Experimental results are reported for dimensions from $n=5$ to $n=14$. The results show that evolutionary search can discover monotone Boolean functions with nonlinearities clearly exceeding those of majority functions, and in several cases approaching the best currently known values for monotone functions. At the same time, the experiments reveal substantial differences between encodings: the balanced truth table encoding performs poorly for larger dimensions, while the standard truth table and genetic programming encodings remain competitive, with genetic programming becoming especially relevant in the largest tested dimensions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Evolutionary search finds monotone BFs with nonlinearity above majority for n<=14, but monotonicity of the outputs needs explicit confirmation.

read the letter

Evolutionary search with a non-monotonicity penalty turns up monotone Boolean functions whose nonlinearity beats the majority function and gets close to known optima in some cases for n up to 14. The three encodings show clear differences in performance, with genetic programming holding its own at the high end. The new part is the penalty term combined with those specific representations to enforce monotonicity while optimizing nonlinearity. The experiments provide direct comparisons to majority and best-known monotone values, which adds usable data points. The work handles the encodings reasonably and notes where the balanced truth table version falls off. That kind of comparative result is helpful for anyone trying similar constrained searches. The main weakness is the thin evidence on whether the outputs are actually monotone. The abstract describes the penalty but gives no indication that it reached zero or that the functions were verified by checking all pairs of inputs. If the penalty allows minor violations that still score high on nonlinearity, the numbers could include non-monotone functions, which would change the interpretation. The lack of run counts, error bars, or reproducibility details makes the claims harder to assess. This is for specialists in Boolean function design for crypto or in evolutionary methods for discrete optimization. A reader in either area can pick up the encoding trade-offs. It should go to peer review. The core idea is sound enough and the results are new enough to warrant referee input, provided the authors add the verification steps and some statistical backing.

Referee Report

3 major / 2 minor

Summary. The paper investigates whether evolutionary algorithms can evolve monotone Boolean functions with nonlinearity exceeding that of majority functions (and approaching known best monotone values) for n=5 to n=14. It compares three encodings—standard truth table, balanced truth table, and tree-based genetic programming—using a composite fitness function that rewards nonlinearity and balancedness while penalizing non-monotonicity. Experiments show that standard truth table and GP encodings are competitive, with GP performing well at larger n, while balanced truth table encoding degrades.

Significance. If the reported functions are verifiably monotone, the work provides concrete evidence that evolutionary search can usefully explore the constrained space of monotone functions beyond hand-crafted constructions such as the majority function. The multi-encoding comparison and the demonstration that nonlinearity can approach known upper bounds for monotone functions would be useful for researchers studying Boolean function properties in cryptography and circuit complexity. The absence of parameter-free derivations or machine-checked proofs is offset by the empirical nature of the contribution.

major comments (3)

[Methods] Methods section (fitness function definition): the non-monotonicity penalty is introduced to steer search toward monotone functions, yet the manuscript provides no formula for the penalty term, no value of the weighting coefficient, and no report of the final penalty values attained by the best individuals. Without these details it is impossible to confirm that the reported nonlinearities belong to strictly monotone functions rather than functions with small violations that still score well on the nonlinearity component.
[Experimental Results] Experimental results (n=5..14 tables/figures): the abstract and results claim nonlinearities “clearly exceeding” majority functions and “approaching the best currently known values,” but no number of independent runs, no standard deviations or error bars, and no statistical comparison are supplied. This leaves the central empirical claim only partially supported and prevents assessment of whether the observed improvements are robust.
[Results] Results section: although the paper states that the evolved functions are monotone, no post-hoc verification (e.g., exhaustive check that f(x) ≤ f(y) whenever x ≤ y in the Boolean lattice, or confirmation that the penalty term is exactly zero) is described for the final reported functions. Such verification is load-bearing for the claim that the nonlinearity figures are valid for the monotone class.

minor comments (2)

[Abstract] The abstract and introduction should explicitly cite the best-known nonlinearity values for monotone functions that the evolved results are said to approach.
[Methods] Notation for the three encodings and the precise definition of balancedness in the fitness function could be clarified with a small table or pseudocode snippet.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. We address each of the major comments point by point below. We believe the suggested revisions will strengthen the paper and will incorporate them in the revised version.

read point-by-point responses

Referee: [Methods] Methods section (fitness function definition): the non-monotonicity penalty is introduced to steer search toward monotone functions, yet the manuscript provides no formula for the penalty term, no value of the weighting coefficient, and no report of the final penalty values attained by the best individuals. Without these details it is impossible to confirm that the reported nonlinearities belong to strictly monotone functions rather than functions with small violations that still score well on the nonlinearity component.

Authors: We agree that the manuscript lacked sufficient detail on the fitness function components. In the revised manuscript, we will explicitly provide the formula for the non-monotonicity penalty term, the value of the weighting coefficient in the composite fitness, and confirm that the best individuals achieved a penalty value of zero. This will allow readers to verify that the reported functions are strictly monotone. revision: yes
Referee: [Experimental Results] Experimental results (n=5..14 tables/figures): the abstract and results claim nonlinearities “clearly exceeding” majority functions and “approaching the best currently known values,” but no number of independent runs, no standard deviations or error bars, and no statistical comparison are supplied. This leaves the central empirical claim only partially supported and prevents assessment of whether the observed improvements are robust.

Authors: The experiments were run multiple times to ensure reliability, but we did not report the number of runs or variability measures in the original submission. We will revise the Experimental Results section to specify the number of independent runs, include standard deviations for the achieved nonlinearities, and add error bars to the relevant figures. While we did not include formal statistical tests, the consistency of the best results across runs supports the claims; we can add a brief discussion of this if required. revision: yes
Referee: [Results] Results section: although the paper states that the evolved functions are monotone, no post-hoc verification (e.g., exhaustive check that f(x) ≤ f(y) whenever x ≤ y in the Boolean lattice, or confirmation that the penalty term is exactly zero) is described for the final reported functions. Such verification is load-bearing for the claim that the nonlinearity figures are valid for the monotone class.

Authors: We concur that a description of the verification process is necessary. Although the search process with the penalty term ensures monotonicity for zero-penalty solutions, we will add to the Results section an explicit statement that post-hoc exhaustive verification was performed on all reported functions, confirming that the penalty term is zero and that the monotonicity condition holds for all comparable pairs in the lattice. revision: yes

Circularity Check

0 steps flagged

No significant circularity in evolutionary search results

full rationale

The paper reports experimental outcomes from applying evolutionary algorithms (truth-table and GP encodings) to optimize Boolean functions under a composite fitness that includes nonlinearity, balancedness, and an explicit non-monotonicity penalty. All measured quantities (nonlinearity values, monotonicity status) are computed directly from the evolved truth tables after search terminates; none are obtained by fitting a parameter to a subset of the same data and then re-reporting it as a prediction. No self-citation chain, uniqueness theorem, or ansatz is invoked to justify the central claim that the evolved functions exceed majority nonlinearity while remaining monotone. The derivation chain is therefore self-contained and consists of standard search against externally defined objectives.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard definitions of monotonicity, nonlinearity, and balancedness from Boolean function theory together with conventional evolutionary-algorithm operators; no new mathematical axioms or invented entities are introduced.

free parameters (1)

non-monotonicity penalty coefficient
Weight used to enforce monotonicity during fitness evaluation; its specific value is not stated in the abstract.

axioms (2)

standard math A Boolean function is monotone increasing if flipping any input bit from 0 to 1 never changes the output from 1 to 0.
Standard definition invoked to define the penalty term.
standard math Nonlinearity is measured by the maximum absolute Walsh-Hadamard coefficient.
Conventional definition used as the primary optimization target.

pith-pipeline@v0.9.0 · 5517 in / 1389 out tokens · 53503 ms · 2026-05-10T05:23:41.915798+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

27 extracted references

[1]

C. Carlet. On the nonlinearity of monotone boolean functions.Cryptography and Communications, 10(6):1051–1061, Oct. 2017

2017
[2]

Carlet.Boolean Functions for Cryptography and Coding Theory

C. Carlet.Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge, 2021

2021
[3]

Carlet, M

C. Carlet, M. Durasevic, D. Jakobovic, L. Mariot, and S. Picek.Look into the Mirror: Evolving Self-dual Bent Boolean Functions, page 161–175. Springer Nature Switzerland, 2024

2024
[4]

Carlet, M

C. Carlet, M. Durasevic, D. Jakobovic, S. Picek, and L. Mariot. A systematic study on the design of odd-sized highly nonlinear boolean functions via evolutionary algorithms.Genetic Programming and Evolvable Machines, 27(1), Dec. 2025

2025
[5]

Carlet, D

C. Carlet, D. Joyner, P. St˘anic˘a, and D. Tang. Cryptographic properties of monotone Boolean functions.Journal of Mathematical Cryptology, 10(1):1–14, 2016

2016
[6]

Carlet and P

C. Carlet and P. Méaux. A complete study of two classes of boolean functions: Direct sums of monomials and threshold functions.IEEE Transactions on Infor- mation Theory, 68(5):3404–3425, 2022

2022
[7]

Djurasevic, D

M. Djurasevic, D. Jakobovic, L. Mariot, and S. Picek. A survey of metaheuristic algorithms for the design of cryptographic Boolean functions.Cryptography and Communications, 15(6):1171–1197, July 2023

2023
[8]

Fuller, E

J. Fuller, E. Dawson, and W. Millan. Evolutionary generation of bent functions for cryptography. InProceedings of the IEEE Congress on Evolutionary Computation, CEC 2003, Canberra, Australia, December 8-12, 2003, pages 1655–1661. IEEE, 2003

2003
[9]

Hrbacek and V

R. Hrbacek and V . Dvorak. Bent function synthesis by means of cartesian genetic programming. In T. Bartz-Beielstein, J. Branke, B. Filipiˇc, and J. Smith, editors, Parallel Problem Solving from Nature – PPSN XIII, pages 414–423, Cham, 2014. Springer International Publishing

2014
[10]

Husa and R

J. Husa and R. Dobai. Designing bent Boolean functions with parallelized linear genetic programming. InProceedings of the Genetic and Evolutionary Computa- tion Conference Companion, GECCO ’17, page 1825–1832, New York, NY , USA,
[11]

Association for Computing Machinery
[12]

Jakobovic, M

D. Jakobovic, M. Ðurasevi´c, S. Picek, and B. Gašperov. Ecf: A c++ framework for evolutionary computation.SoftwareX, 27:101640, 2024

2024
[13]

G. Kalai. Threshold phenomena and influences.Computational Complexity and Statistical Physics, pages 25–60, 2006. Lecture notes / survey

2006
[14]

A. Kerdock. A class of low-rate nonlinear binary codes.Information and Control, 20(2):182 – 187, 1972. 15

1972
[15]

A. D. Korshunov. Monotone boolean functions.Russian Mathematical Surveys, 58(5):929–1001, 2003

2003
[16]

F. J. MacWilliams and N. J. A. Sloane.The Theory of Error-Correcting Codes. Elsevier, Amsterdam, North Holland, 1977. ISBN: 978-0-444-85193-2

1977
[17]

Manzoni, L

L. Manzoni, L. Mariot, and E. Tuba. Balanced crossover operators in genetic algorithms.Swarm Evol. Comput., 54:100646, 2020

2020
[18]

Mariot, M

L. Mariot, M. Saletta, A. Leporati, and L. Manzoni. Heuristic search of (semi-)bent functions based on cellular automata.Nat. Comput., 21(3):377–391, 2022

2022
[19]

Millan, A

W. Millan, A. Clark, and E. Dawson. Heuristic design of cryptographically strong balanced Boolean functions. In K. Nyberg, editor,Advances in Cryptology — EUROCRYPT’98, pages 489–499, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg

1998
[20]

O’Donnell.Analysis of Boolean Functions

R. O’Donnell.Analysis of Boolean Functions. Cambridge University Press, 2014

2014
[21]

Paulevé and S

L. Paulevé and S. Sené. Boolean networks and their dynamics: the impact of updates.International Journal of Molecular Sciences, 23(15):8671, 2022

2022
[22]

Picek and D

S. Picek and D. Jakobovic. Evolving algebraic constructions for designing bent Boolean functions. InProceedings of the Genetic and Evolutionary Computa- tion Conference 2016, GECCO ’16, page 781–788, New York, NY , USA, 2016. Association for Computing Machinery

2016
[23]

Picek, K

S. Picek, K. Knezevic, L. Mariot, D. Jakobovic, and A. Leporati. Evolving bent quaternary functions. In2018 IEEE Congress on Evolutionary Computation, CEC 2018, Rio de Janeiro, Brazil, July 8-13, 2018, pages 1–8. IEEE, 2018

2018
[24]

R. Poli, W. B. Langdon, and N. F. McPhee.A Field Guide to Genetic Programming. lulu.com, 2008

2008
[25]

O. Rothaus. On “bent” functions.Journal of Combinatorial Theory, Series A, 20(3):300 – 305, 1976

1976
[26]

L. Yan, J. Cui, J. Liu, G. Xu, L. Han, A. Jolfaei, and X. Zheng. Iga: An improved genetic algorithm to construct weightwise (almost) perfectly balanced boolean functions with high weightwise nonlinearity. InProceedings of the 2023 ACM Asia Conference on Computer and Communications Security, ASIA CCS ’23, page 638–648, New York, NY , USA, 2023. Association...

2023
[27]

M. Yang, Q. Meng, and H. Zhang. Evolutionary design of trace form bent functions. Cryptology ePrint Archive, Paper 2005/322, 2005. https://eprint.iacr.org/ 2005/322. 16

2005