All Questions
25 questions
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
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
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)\...
- 93
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
2
votes
0
answers
111
views
Standard interpretation of permanents (of orthogonal included) over finite fields
Given a $0/1$ matrix in $\mathbb Z^{n\times n}$ the standard interpretation of permanent of the matrix is the number of perfect matchings in the underlying $2n$ vertex balanced bipartite graph with ...
- 13.9k
14
votes
2
answers
655
views
Number triangle
This question arose just out of curiosity. Note the triangle of 0-1's below, whose construction is as follows. Choose any number, say 53 as done here. The first line of the triangle is the binary ...
- 1,216
5
votes
1
answer
287
views
Given a symmetric polynomial in F_q, write it in terms as elementary symmetric polynomials. How to find out the coefficient?
Consider the finite field $F_q$, where $q$ is a power of an odd prime and $N$ is a power of $q$. We have a homogeneous symmetric polynomial
$$
E_{l,s}(x) = \sum_{\substack{l_1+l_2+\cdots +l_s=l \\ l_i\...
3
votes
0
answers
147
views
Under what conditions on $A$ and $v$ is the size of the sumset $v \cdot A + A$ over $\mathbb{F}_p$ equal or close to $|A|^2$?
Let $p$ be a prime, let $A$ be a subset of $\mathbb{F}_p$, and let $v \in \mathbb{F}_p \setminus \{0\}$.
Under what conditions is $|v \cdot A + A|$ (that is, $|\{ va + b : a \in A,\ b \in A \}|$) ...
16
votes
2
answers
1k
views
Examples of problems where considering "discrete analogues" has provided insight or led to a solution of the original problem
The Kakeya conjecture posits that any Kakeya set in $\mathbb{R}^n$ has dimension $n$.
A discrete (finitized?) version of this problem is the Finite Field Kakeya conjecture, which was proved by Dvir ...
2
votes
1
answer
192
views
A Vandermonde-type system
For a prime $p$ and $a_1,\dotsc,a_n\in\mathbb F_p^\times$, consider the system of equations
$$ \begin{cases}
\begin{align}
a_1 + \dotsb + a_n &= 0 \\
a_1x_1 + \dotsb + a_nx_n &...
- 23k
0
votes
2
answers
295
views
Permutations of squares and finite fields
Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$, and let
$$S(n)=\bigg\{\sum_{k=1}^nk^2\pi(k)^2:\ \pi\in S_n\}.$$
Motivated by Question 316142 of mine, here I ask the following ...
- 15.6k
1
vote
0
answers
154
views
On the set $\{\sum_{k=1}^n \lambda_ka_k:\ a_1,\ldots,a_k\ \text{are distinct elements of}\ A\}$
For a field $F$ let $p(F)=p$ if the characteristic of $F$ is a prime $p$, and $p(F)=+\infty$ if $F$ is of characteristic zero.
In 2007 I considered the linear extension of the Erdos-Heilbronn ...
- 15.6k
6
votes
1
answer
640
views
Upperbounding a sum of Legendre-Symbols
Let $p$ be a prime with $p\equiv 3 \mod 4$, for any $\mathcal{I} \subset \lbrace 0,...,p-1 \rbrace $ and any $\mathcal{J} \subset \lbrace 0,...,p-1 \rbrace $ with $\vert\mathcal{I}\vert \leq \sqrt{p} $...
- 93
0
votes
1
answer
190
views
$k$-covering $\mathbb F_p$ with $k+1$ sets
Let $p$ be a (large) prime.
How large can a set $C\subset\mathbb F_p$ be given that there is a function $f\colon\mathbb F_p^\times\to\mathbb F_p$ such that for every element $g\in \mathbb F_p$, ...
- 23k
3
votes
1
answer
177
views
Double-covering $\mathbb F_p$ with three sets
Let $p$ be a (large) prime.
Does there exist a function $f\colon\mathbb F_p^\times\to\mathbb F_p$ such that the three sets
$$ \{f(z)-z\colon z\in\mathbb F_p^\times\},\ \{f(z)\colon z\in\mathbb ...
- 23k
5
votes
0
answers
205
views
Polynomials representing locally constant functions
Let $K$ be a finite field with $p$ elements.
(a) Let $f\in K\lbrack x\rbrack$ be such that (i) $\deg(f)<p$ and (ii) $f(2x) = f(x)$ for $\geq (1-\epsilon) p$ values of $x$ in $K$. What can we say ...
- 20.2k
4
votes
1
answer
382
views
Counting couples of square-free polynomials over finite fields
I have a curve defined by the following equations over the finite field $\mathbb{F}_q$ with $q=p^r$ with $p \geq 3$:
$$C_{h_1,h_2}:\begin{cases} y_1^2=h_1(t) & \\
y_2^2=h_2(t) &...
- 41
6
votes
1
answer
372
views
A parity counting problem for subsets over finite fields
Let ${\mathbb F}_p$ be the prime field of $p$ elements and $b$ be an element in ${\mathbb F}_p$.
For a subset $T\subseteq {\mathbb F}_p$, define
$$Bias(T)=|N_e( {\mathbb F}_p,b)-N_o( {\mathbb F}_p,b)|...
- 121
4
votes
0
answers
215
views
What is the function like when its Mobius inversion is $\sum_{w|r, (w,t)=1}\mu(w)q^{r/w}$?
Everyone, I am now reading a paper named The Irreducible Factors of $(cx+d)x^{q^m}-(ax+b)$ over $GF(q)$, http://qjmath.oxfordjournals.org/content/14/1/61.extract. And I’m confused with one of its ...
- 41
20
votes
2
answers
2k
views
Sums of powers mod p
For prime $p > 7$ with $p-1=rs$, $r>1$, $s>1$, let $A=\{x^r|x \in \mathbb{Z}_p\}$ and $B = \{x^s|x \in \mathbb{Z}_p\}$. If $g$ is a primitive root mod $p$ then $A = \{0\} \cup \{g^{ir}|0 \leq ...
- 619
67
votes
6
answers
7k
views
How to recognise that the polynomial method might work
A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson.
Theorem. Let $(a_1,b_1),\dots,(...
- 29k
7
votes
2
answers
476
views
A quadratic form
Let $q$ be a power of 2. Let $P$ be the set of polynomials in
$F_q [x]$ of degree d or less.
Let $\mathbb{Z}$ be the ring of integers. For any $f \in P$, let $\psi(f)$ be the
number of distinct ...
- 503
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$...
- 118k