The classification of Boolean degree 1 functions in high-dimensional finite vector spaces

Ihringer, Ferdinand

doi:10.1090/proc/16957

The classification of Boolean degree $1$ functions in high-dimensional finite vector spaces
HTML articles powered by AMS MathViewer

by Ferdinand Ihringer;

Proc. Amer. Math. Soc. 152 (2024), 5355-5365

DOI: https://doi.org/10.1090/proc/16957

Published electronically: October 9, 2024

HTML | PDF | Request permission

Abstract:

We classify the Boolean degree $1$ functions of $k$-spaces in a vector space of dimension $n$ (also known as Cameron-Liebler classes) over the field with $q$ elements for $n \geq n_0(k, q)$. This also implies that two-intersecting sets with respect to $k$-spaces do not exist for $n \geq n_0(k, q)$. Our main ingredient is the Ramsey theory for geometric lattices.

References

A. Blokhuis, M. De Boeck, and J. D’haeseleer, Cameron-Liebler sets of $k$-spaces in $\textrm {PG}(n,q)$, Des. Codes Cryptogr. 87 (2019), no. 8, 1839–1856. MR 3974804, DOI 10.1007/s10623-018-0583-1
A. A. Bruen and Keldon Drudge, The construction of Cameron-Liebler line classes in $\textrm {PG}(3,q)$, Finite Fields Appl. 5 (1999), no. 1, 35–45. MR 1667101, DOI 10.1006/ffta.1998.0239
P. J. Cameron and R. A. Liebler, Tactical decompositions and orbits of projective groups, Linear Algebra Appl. 46 (1982), 91–102. MR 664699, DOI 10.1016/0024-3795(82)90029-5
Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, and Marc Vinyals, Complexity measures on the symmetric group and beyond, 12th Innovations in Theoretical Computer Science Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 185, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021, pp. Art. No. 87, 5. MR 4214331, DOI 10.1305/ndjfl/1040046140
Jan De Beule, Jeroen Demeyer, Klaus Metsch, and Morgan Rodgers, A new family of tight sets in $\mathcal Q^+(5,q)$, Des. Codes Cryptogr. 78 (2016), no. 3, 655–678. MR 3459217, DOI 10.1007/s10623-014-0023-9
Jan De Beule, Jonathan Mannaert, and Leo Storme, Cameron-Liebler $k$-sets in subspaces and non-existence conditions, Des. Codes Cryptogr. 90 (2022), no. 3, 633–651. MR 4390573, DOI 10.1007/s10623-021-00995-0
J. De Beule, J. Mannaert, and L. Storme, On two non-existence results for Cameron-Liebler $k$-sets in $PG(n, q)$, arXiv:2403.00519 [math.CO], 2024.
Keldon Wayne Drudge, Extremal sets in projective and polar spaces, ProQuest LLC, Ann Arbor, MI, 1998. Thesis (Ph.D.)–The University of Western Ontario (Canada). MR 2698237
David Ellis, Ehud Friedgut, and Haran Pilpel, Intersecting families of permutations, J. Amer. Math. Soc. 24 (2011), no. 3, 649–682. MR 2784326, DOI 10.1090/S0894-0347-2011-00690-5
Tao Feng, Koji Momihara, Morgan Rodgers, Qing Xiang, and Hanlin Zou, Cameron-Liebler line classes with parameter $x=\frac {(q+1)^2}3$, Adv. Math. 385 (2021), Paper No. 107780, 31. MR 4256140, DOI 10.1016/j.aim.2021.107780
Tao Feng, Koji Momihara, and Qing Xiang, Cameron-Liebler line classes with parameter $x=\frac {q^2-1}{2}$, J. Combin. Theory Ser. A 133 (2015), 307–338. MR 3325637, DOI 10.1016/j.jcta.2015.02.004
Yuval Filmus, Friedgut-Kalai-Naor theorem for slices of the Boolean cube, Chic. J. Theoret. Comput. Sci. , posted on (2016), Art. 14, 17. MR 3578425, DOI 10.4086/cjtcs.2016.014
Yuval Filmus, Junta threshold for low degree Boolean functions on the slice, Electron. J. Combin. 30 (2023), no. 1, Paper No. 1.55, 20. MR 4564831, DOI 10.37236/11115
Yuval Filmus and Ferdinand Ihringer, Boolean degree 1 functions on some classical association schemes, J. Combin. Theory Ser. A 162 (2019), 241–270. MR 3874601, DOI 10.1016/j.jcta.2018.11.006
Yuval Filmus and Ferdinand Ihringer, Boolean constant degree functions on the slice are juntas, Discrete Math. 342 (2019), no. 12, 111614, 7. MR 3990024, DOI 10.1016/j.disc.2019.111614
B. Frederickson and L. Yepremyan, Vector space Ramsey numbers and weakly Sidorenko affine configurations, arXiv:2308.13489v1 [math.CO], 2023.
Ehud Friedgut, Gil Kalai, and Assaf Naor, Boolean functions whose Fourier transform is concentrated on the first two levels, Adv. in Appl. Math. 29 (2002), no. 3, 427–437. MR 1942632, DOI 10.1016/S0196-8858(02)00024-6
Alexander L. Gavrilyuk and Ivan Yu. Mogilnykh, Cameron-Liebler line classes in $PG(n,4)$, Des. Codes Cryptogr. 73 (2014), no. 3, 969–982. MR 3248525, DOI 10.1007/s10623-013-9838-z
Alexander L. Gavrilyuk and Ilia Matkin, Cameron-Liebler line classes in $\rm PG(3,5)$, J. Combin. Des. 26 (2018), no. 12, 563–580. MR 3875128, DOI 10.1002/jcd.21625
Patrick Govaerts and Tim Penttila, Cameron-Liebler line classes in $\textrm {PG}(3,4)$, Bull. Belg. Math. Soc. Simon Stevin 12 (2005), no. 5, 793–804. MR 2241344
R. L. Graham, K. Leeb, and B. L. Rothschild, Ramsey’s theorem for a class of categories, Advances in Math. 8 (1972), 417–433. MR 306010, DOI 10.1016/0001-8708(72)90005-9
I. A. Matkin, Cameron-Liebler line classes of $\textrm {PG}(n,5)$, Tr. Inst. Mat. Mekh. 24 (2018), no. 2, 158–172 (Russian, with English and Russian summaries). MR 3853330, DOI 10.21538/0134-4889-2018-24-2-158-172
Francesco Mazzocca and Giuseppe Tallini, On the nonexistence of blocking-sets in $\textrm {PG}(n,q)$ and $\textrm {AG}(n,q),$ for all large enough $n$, Simon Stevin 59 (1985), no. 1, 43–50. MR 795270
Klaus Metsch, The non-existence of Cameron-Liebler line classes with parameter $2<x\leqslant q$, Bull. Lond. Math. Soc. 42 (2010), no. 6, 991–996. MR 2740019, DOI 10.1112/blms/bdq057
Aaron D. Meyerowitz, Cycle-balanced partitions in distance-regular graphs, J. Combin. Inform. System Sci. 17 (1992), no. 1-2, 39–42. MR 1216964
Hans Jürgen Prömel and Bernd Voigt, Recent results in partition (Ramsey) theory for finite lattices, Discrete Math. 35 (1981), 185–198. MR 620671, DOI 10.1016/0012-365X(81)90207-7
Maria Tallini Scafati, Calotte di tipo $(m,\,n)$ in uno spazio di Galois $S_{r,q}$, Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Nat. (8) 53 (1972), 71–81 (1973) (Italian, with English summary). MR 349436
Maria Tallini Scafati, Sui $k$-insiemi di uno szazio di Galois $S_{r,q}$ a due soli caratteri nella dimensione $d$, Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Nat. (8) 60 (1976), no. 6, 782–788 (Italian, with English summary). MR 461274
B. Voigt, Ramsey-Saetze für endliche Geometrien und endliche abelsche Gruppen, PhD thesis, Universität Bielefeld, 1978.