All Questions
Tagged with finite-fields co.combinatorics
136 questions
8
votes
1
answer
531
views
How large can the dimension of a 'Span of powers of a finite field basis' be?
Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector ...
CommunityBot
- 1
4
votes
0
answers
108
views
Differential duality: Triangular codes vs. VT codes / Single-substitution vs. Single-deletion
Here is the introduction to my problem:
Codes correcting single-deletion. Let $q$ and $n$ be non-negative integers, and let $\mathbf{x}= \left ( x_{1}, x_{2}, \ldots, x_{n} \right )\in\mathbb{Z}_{q}^{...
- 10.4k
0
votes
0
answers
80
views
Solution modulo $9$ of certain linear equation implies triviality modulo $3$
Question: Let $k \geq 2$ and $r \geq 4$ be two natural numbers. We are given eight integers $\nu_{ij} \geq 0$ for every $1 \leq i \leq k$ and $1 \leq j \leq r$ such that the following two conditions ...
- 119
11
votes
2
answers
386
views
Bounds for the difference in the number of ones in $M$ and $M^{-1}$
If $M$ is a full rank $n$ by $n$ binary matrix over $\mathbb{F}_2$, how much larger or smaller can the number of $1$s in $M^{-1}$ be, compared to the number of $1$s in $M$?
Clearly the identity matrix ...
- 109k
3
votes
2
answers
303
views
Asymptotics of A000613
The general linear group $GL_n(\mathbb{F}_2)$ acts on the powerset $2^{{\mathbb{F}_2}^n \setminus \{0\}}$ by multiplication: $A \cdot S := \{Ax \in {\mathbb{F}_2}^n : \, x \in S\}$, for an invertible ...
- 148k
2
votes
1
answer
262
views
Randomly fixing elements and transcendence degree
Given $f_1,\ldots,f_n \in \mathbb{F}_q[x_1,\ldots,x_m]$ such that $\deg(f_i) \leq d < q$. Suppose we have for some $1 \leq j \leq m$
$$ \operatorname{trdeg}_{\mathbb{F}(x_1,\ldots,x_j)}\{f_1,\ldots,...
- 341
2
votes
0
answers
187
views
Matrix with elementary symmetric polynomials as entries
Let $n\geq 1$, and for each $j=1,\ldots, n+1$ let $\mathbf{X}_{j}=(X_{j1},\ldots, X_{jn})$ be $n$ variables. Let $M$ be the $(n+1)\times (n+1)$ matrix whose $(i,j)$-th entry is $$M_{ij}=(-1)^i e_{i-1}(...
0
votes
0
answers
53
views
A question on bounding the size of the polynomial
Suppose we are given the following n polynomials in $\bar{\mathbb{F}}_2[x_1,...,x_n]$:
$f_1 = x_1 + x_n^2$
$f_2 = x_2 + x_1^2$
$\cdot$
$\cdot$
$f_{n-3} = x_{n-3} + x_{n-4}^2$
$f_{n-2} = x_{n-2} + x_{n-...
- 341
13
votes
0
answers
188
views
Why is $ULU=NU$ (a refinement of $|N|=q^{n^2-n}$)?
Let $G=GL_n(\mathbb{F}_q)$, $U$, $L$, $N$ the subsets of upper-triangular unipotent, lower-triangular unipotent, all unipotent matrices respectively. Then $ULU=NU$ means that for any $g\in G$ the ...
- 3,772
5
votes
2
answers
139
views
Sets blocking every $2$-flat in $AG(n,2)$
The following may be well-known $-$ but not known to me:
What is the smallest possible size of a set in ${\mathbb F}_2^n$ that blocks every $2$-flat?
Here "blocks" means "have a non-empty ...
- 131
2
votes
1
answer
119
views
Asymptotic size of largest subset in $\mathbb F_p^2$ defining only lines of different slopes
Suppose that all lines defined by pairs of distinct elements in a subset of $\mathbb F_p^2$ have different slopes. How large can such a subset be asymptotically (for primes $p\rightarrow \infty$)?
...
- 10.4k
0
votes
1
answer
189
views
Constructing a family of $3$-wise independence functions from $\mathbb{Z}_p^n \rightarrow \mathbb{Z}_p$
A family of function hash functions $\mathcal{H}:\{h:N\rightarrow M\}$ is call $k$-wise independent if whenenver $h$ is drawn uniformly from $\mathcal{H}$, let $x_1,\ldots,x_k$ be distinct elements of ...
- 10.4k
0
votes
1
answer
146
views
Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically?
I am a little confused with the relationship between various bounds for error correcting codes.
Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically? That is, is ...
1
vote
0
answers
71
views
Bias of $a^k / q$ modulo $q$?
Let $q$ be a prime. Let $0< a < q$ be an integer so that it is primitive modulo $q$. Let $k$ be a random integer up to $q-1$. Consider
$$a^k = b_k + q * c_k$$
as $k$ varies modulo $q^2$. So $b_k$...
- 591
1
vote
0
answers
91
views
Functions that take quadratic residues to non quadratic residues
Let $p$ be prime and $Q$ be the set of integers $x$ mod $p$ so that $x^2-1$ is a quadratic residue. Let $Q^c$ be the complement of $Q$. If we don't consider $x = 1$ then these two sets have the same ...
- 591
4
votes
0
answers
263
views
Cosine Modulo $p$?
Consider the integers modulo a prime $p$. I'm looking for a nice polynomial function that acts as a sort of "cosine" on the integers modulo $p$. Specifically, I'm looking for solutions to ...
- 591
1
vote
1
answer
133
views
Constant term of a power modulo a polynomial
I'm interested in the constant term of $$(x+k)^m \in F_p[x]$$
modulo a polynomial $q(x)$ over the field $F_p$. The polynomial $q(x)$ is relatively simple in practice, take $q(x) = x^6 -2x^3+3$, for an ...
- 34.3k
1
vote
1
answer
333
views
Szemerédi–Trotter type theorem in finite field
This question is about the content of this paper by J. Bourgain, N. Katz, T. Tao.
In the final step (page 18) of the proof of Szemerédi-Trotter type theorem, we have already known
$$|A''+A''|\lesssim ...
- 13k
2
votes
0
answers
162
views
Determining the multiple solutions for $\mathrm{GF}(2)$ discrete logarithms of polynomials with partially known coefficients
I have an LFSR, essentially $x^k \bmod p(x)$ for some characteristic primitive polynomial of degree $N$ with coefficients in $\mathrm{GF}(2)$, as outlined in Clark and Weng's article: it has a period $...
- 63.9k
1
vote
0
answers
162
views
Number of full-rank binary matrices with given column Hamming weights [closed]
What is the number of $m \times n$ matrices over $\mbox{GF}(2)$ that share the following constraints :
They have full rank ($\mbox{rank} = m$, given that $m<n$).
Their columns have the given ...
2
votes
1
answer
612
views
Inner product over finite field
sorry for informals but is my first post.
In Coding theory (exactly in Coding theory a first course - San ling and Chaoping) found this definition:
$\langle , \rangle :\mathbb{F}_q^n\times\mathbb{F}_q^...
3
votes
0
answers
293
views
Approximate versions of Segre's Theorem
Consider projective $2$-space over a finite field of odd prime characteristic $p$. We say a set of points, $A$, in this space is an arc if any line meets it in at most two points. We say that an arc ...
- 13k
2
votes
1
answer
185
views
How many ways are there to pick $n$ points on the finite affine plane $(\Bbb F_q)^2$ such that no three are collinear?
How many ways are there to pick $n$ points on the finite affine plane $(\Bbb F_q)^2$ such that no three are collinear?
For example, how many ways can we pick $5$ points on $\Bbb F_{32}\times\Bbb F_{32}...
- 17.9k
4
votes
1
answer
561
views
Why should it be hard to generalize Dvir's proof of the finite field Kakeya conjecture to the Euclidean case?
Let $q$ be prime and let
$q\delta \sim 1.$ Let $K$ be any set of $C_n\delta$-separated tubes in $B(0,2)$, where $C_n$ is some constant depending on $n$. Let us consider a grid of $q^n$ points scaled ...
4
votes
1
answer
237
views
Intersection of the general linear group $\text{GL}_n(\mathbb{F}_q)$ and an affine subspace over a finite field
Let $\mathbb{F}_q$ be a finite field of $q$ elements, let $\text{M}_n(\mathbb{F}_q)$ be the vector space of $n \times n$ matrices over $\mathbb{F}_q$, let $\text{GL}_n(\mathbb{F}_q)$ be the group of $...
- 156k
6
votes
0
answers
314
views
Number of square-free polynomials over a finite field - a combinatorial interpretation?
Cross-posted from MSE. The question has remained unanswered for six years but I still like it!
One can show using zeta functions that the number of (monic)square-free polynomials of degree $n$ over a ...
- 7,746
1
vote
0
answers
84
views
Constructing k-wise independent variables over a general set
We have seen in class a polynomials based construction that builds in $O(n^k)$ time, $n$ random variables, $k$-wise independent, over a field with $n$ elements. More specifically, you generate all the ...
- 11
1
vote
0
answers
130
views
Maximal subsets of affine or projective space with no three collinear points
Let ${\mathbb A}^n_q$ and ${\mathbb P}^n_q$ be affine and projective spaces of dimension $n$ over a field of order $q$.
Say that a subset of either ${\mathbb A}^n_q$ or ${\mathbb P}^n_q$ is generic if ...
- 63.9k
4
votes
0
answers
104
views
Visiting zero-sum triples in a vector space
Is it true that for any set $A\subset\mathbb F_5^n$ satisfying $A\cap(-A)=\varnothing$, there is a subset $A'\subseteq A$ such any triple $(a,b,c)\in A\times A\times A$ with $a+b+c=0$ has exactly one ...
- 23k
4
votes
1
answer
266
views
Can we explicitly compute this "shift"-quantity over Boolean functions $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$?
This question is a follow-up of this question.
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and suppose that $n$ is odd.
Question: Can we compute the exact minimum $$A:=
\min_{u:\mathbb{...
CommunityBot
- 1
1
vote
1
answer
391
views
System of equations - Proof that a solution exists
Let $ a = (a_1,a_2, \ldots,a_{10})\in \{ 0,1\}^{10}$ be a binary vector of length $10$.
Question: Without using a computer-aided method, how to prove that there exists binary vectors $x_{i,j} \in \{ ...
- 34.3k
1
vote
0
answers
150
views
Counting non-zero Gramians of Grassmanians over finite field
In case of $\mathbb{F}_{2}$, we can obtain the number of all reduced row echelon forms (so called Grassmannians) for some m$\times$n full rank matrices by the following gaussian polynomial,
$$
\binom{...
- 11
0
votes
0
answers
99
views
Invertible matrices with bounded nonnegative coefficients
I am teaching a class in linear algebra and I asked myself the following question: what is the chance to get an invertible matrix if I write a random one? My impulsive answer is "very likely"...
CommunityBot
- 1
22
votes
1
answer
969
views
Grothendieck on polyhedra over finite fields
In Grothendieck's Sketch of a Programme he spends a few pages discussing polyhedra over arbitrary rings and concludes with some intriguing remarks on specializing polyhedra over their "most ...
- 12.9k
4
votes
1
answer
212
views
Order of a rational function on $\mathbb{F}_p$
Let $a$ be an element of $\mathbb{F}_p$, which is not a quadratic residue.
Define $$f(x) = \frac{x + a}{x+1},$$ which is a rational function on $\mathbb{F}_p$. In fact, if we set $f(-1)=\infty$ and $f(...
- 12.9k
10
votes
2
answers
882
views
The maximal subset of a finite field where the sum of any subset is non-zero
Given a finite field $\mathbb{F}_q$ with $q=p^m$ where $p$ is the characteristic.
For any subset $S=\{a_1,\dots,a_n\}$ of $\mathbb{F}_q$, if any partial sum (i.e. the sum of elements in a non-empty ...
- 23k
9
votes
1
answer
425
views
Are there functions $\mathbb{F}_2^n \to \mathbb{F}_2$ satisfying these special relations?
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and let
$u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$. Suppose that $n$ is odd.
Is it possible that
$$
\sum_{x \in \mathbb{F}_2^n}(-1)^{u(x)+u(...
- 656
23
votes
4
answers
3k
views
Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words.
Let $q$ be a power of a prime. It's well-known that the function $B(n, q) = \frac{1}{n} \sum_{d | n} \mu \left( \frac{n}{d} \right) q^d$ counts both the number of irreducible polynomials of degree $n$...
- 3,432
1
vote
1
answer
153
views
Schur complement and depermuting an algorithm for $\mathsf{determinant}\bmod2$
Let $$M=\begin{bmatrix}A&B\\C&D\end{bmatrix}$$ be a matrix in $\mathbb F_2^{n\times n}$ where $A\in\mathbb F_2$ and $D\in\mathbb F_2^{(n-1)\times(n-1)}$ are square.
Through the determinant ...
- 63.9k
2
votes
0
answers
203
views
Can the relation between count of commuting pairs and conjugacy classes for finite groups be generalized to semigroups?
It is well-known that number of pairs of commuting elements in finite group G is equal to number of conjugacy classes multiplied by cardinality of G.
More generally here (MO275769) Qiaochu Yuan ...
- 24.9k
0
votes
0
answers
54
views
Rank decomposition of matrices over $\mathbb F_2$
Given an integer matrix $M\in\mathbb Z^{n\times n}$ of real rank $k$ what is the minimum and maximum number of rank $1$ matrices $B_1$ to $B_t$ we require so that $M\equiv\sum_{i=1}^tB_i\bmod 2$?
If $...
- 13.9k
2
votes
0
answers
100
views
Sum of binary quadratic forms over inputs of equal Hamming weight
$\DeclareMathOperator{\field}{\mathbb{F}}$
Let $n$ be a positive integer, and let $q : \field_2^{n} \rightarrow \field_2$ be a quadratic form, specified in coordinates as
$$q(x)=\sum_{i =1}^n \alpha_i ...
- 34.3k
7
votes
2
answers
440
views
How to count the number of tensors over a finite field of tensor rank $r$?
For simplicity, work over $\mathbb F_2$ and only consider order-$3$ equilateral tensors. For $r\in\mathbb Z_{>0}$, how many tensors $\mathfrak{T}\in\mathsf{Ten}_{n}^{\otimes 3}(\mathbb F_2)$ are ...
- 2,179
2
votes
0
answers
157
views
On hypergeometric functions over finite fields
Let $\mathbb{F}_q$ be a finite field of $q$ elements. Let $A,B,C,\cdots$ denote the multiplicative characters over $\mathbb{F}_q$, and let $\overline{A}$ denote the inverse of $A$, i.e., $A(x)\...
- 3,587
2
votes
1
answer
217
views
Low-Hamming weight vectors in low-dimensional subspaces of $\mathbb{F}_p^n$
What is the maximum number vectors of Hamming weight at most $w$ in a $d$-dimensional subspace of $\mathbb{F}_p^n$, where $w,d,p$ are constant and $p$ is odd. (The Hamming weight is the number of ...
- 109k
4
votes
1
answer
317
views
On the real and finite field rank of a $0/1$ matrix - I
Let $M\in\{-1,0,+1\}^{n\times n}$ be a matrix of rank $r$.
Consider the matrix $f(M)\in\{0,+1\}^{mn\times mn}$ where $0$ in $M$ is replaced by $m\times m$ all $0$ matrix, $+1$ in $M$ is replaced by $m\...
- 1,432
1
vote
0
answers
88
views
On the real and finite field rank of a $0/1$ matrix - II
Let $M\in\{-\ell,\dots,-1,0,+1,\dots,+\ell\}^{n\times n}$ be a matrix of rank $r$ where $\ell\geq1$ such that there is a permutation matrix in $\{0,1\}^{m\times m}$ of order $2\ell$.
Fix a permutation ...
- 13.9k
7
votes
2
answers
589
views
On a matrix problem in the field $\mathbb F_2$
Given $M$ a symmetric matrix in $\mathbb F_2^{n\times n}$ having $\mathsf{det}_\mathbb R(M)\neq0$ (non-singular in reals) and satisfying $PMP'=(M+J+I)$ or $P(M+J+I)P'=M$ where $P$ is a permutation ...
- 44.4k
1
vote
0
answers
96
views
Polynomial composition utilizing polynomials in two different finite fields
At every $n\in\mathbb N$ (all polynomials are of degree $O(1)$) is there $g_{3,1}^{(n)},\dots,g_{3,k}^{(n)}\in\mathbb F_3[x_1,\dots,x_n]$ at $k=\mathsf{poly}(n)$ and $g_2^{(n)}\in\mathbb F_2[x_1,\dots,...
- 13.9k
4
votes
1
answer
273
views
Dominating sets in subtournaments of the Paley tournament
For a tournament $T$, let $\mathrm{dom}(T)$ be the order of a smallest dominating set in $T$. Let $q$ be a prime power congruent to 3 mod 4 and let $T_q$ be the Paley tournament on $q$ vertices.
Is ...
- 7,836