On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors

• URL: http://arxiv.org/abs/2405.08741v1
• Date: Tue, 14 May 2024 16:30:28 GMT
• Title: On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors
• Authors: Maximilien Gadouleau, Luca Mariot, Federico Mazzone,
• Abstract summary: We characterize maximal families over the binary field $mathbbF$. Our findings prompt several more open questions, which we plan to address in an extended version of this work.
• Score: 1.249418440326334
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the construction of maximal families of polynomials over the finite field $\mathbb{F}_q$, all having the same degree $n$ and a nonzero constant term, where the degree of the GCD of any two polynomials is $d$ with $1 \le d\le n$. The motivation for this problem lies in a recent construction for subspace codes based on cellular automata. More precisely, the minimum distance of such subspace codes relates to the maximum degree $d$ of the pairwise GCD in this family of polynomials. Hence, characterizing the maximal families of such polynomials is equivalent to determining the maximum cardinality of the corresponding subspace codes for a given minimum distance. We first show a lower bound on the cardinality of such families, and then focus on the specific case where $d=1$. There, we characterize the maximal families of polynomials over the binary field $\mathbb{F}_2$. Our findings prompt several more open questions, which we plan to address in an extended version of this work.

Related papers

• Bridging Weighted First Order Model Counting and Graph Polynomials [6.2686964302152735]
  Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a domain. We define Weak Connectedness Polynomial and Strong Connectedness Polynomials for first-order logic sentences.
  arXiv  Detail & Related papers  (2024-07-16T16:01:25Z)
• Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
  We revisit certain problems of pose estimation based on 3D--2D correspondences between features which may be points or lines. We show experimentally that the resulting solvers are numerically stable and fast.
  arXiv  Detail & Related papers  (2024-04-25T12:09:16Z)
• Higher Level Completeness for Permutation Polynomials [0.0]
  Generalising the concept of a complete permutation over a finite field, we define completness to level $kge1$ in fields of odd characteristics. We construct two families of characteristics that satisfy the condition of high level completeness for all finite fields.
  arXiv  Detail & Related papers  (2023-10-19T04:47:53Z)
• Dimension-free Remez Inequalities and norm designs [48.5897526636987]
  A class of domains $X$ and test sets $Y$ -- termed emphnorm -- enjoy dimension-free Remez-type estimates. We show that the supremum of $f$ does not increase by more than $mathcalO(log K)2d$ when $f$ is extended to the polytorus.
  arXiv  Detail & Related papers  (2023-10-11T22:46:09Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• Progressive approximation of bound states by finite series of square-integrable functions [0.0]
  We use the "tridiagonal representation approach" to solve the time-independent Schr"odinger equation for bound states in a basis set of finite size.
  arXiv  Detail & Related papers  (2022-02-20T00:25:35Z)
• Classical Codes and Chiral CFTs at Higher Genus [0.0]
  We derive explicit expressions for the higher genus partition functions of a specific class of CFTs: code CFTs. This work provides a step towards a full understanding of the constraints from higher genus modular invariance on 2d CFTs.
  arXiv  Detail & Related papers  (2021-12-09T19:00:04Z)
• Density theorems with applications in quantum signal processing [0.0]
  We study the approximation capabilities of two families of univariates that arise in applications of quantum signal processing. We propose two subfamilies of monotone and non-monotone approximations. For the non-monotone case, under some additional assumptions, we provide an iterative algorithm that finds the optimal approximation.
  arXiv  Detail & Related papers  (2021-11-13T20:00:21Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
  We study the algorithmic task of finding a large independent set in a sparse ErdHos-R'enyi random graph. We show that the class of low-degree algorithms can find independent sets of half-optimal size but no larger.
  arXiv  Detail & Related papers  (2020-10-13T17:26:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.