All Questions
36 questions
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
47
votes
3
answers
3k
views
A curious identity related to finite fields
To three elements $a_1$, $a_2$, $a_3$ in the finite field $\mathbb F_q$
of $q$ elements we associate the number $N(a_1,a_2,a_3)$
of elements $a_0\in \mathbb F_q$ such that the polynomial
$x^4+a_3x^3+...
- 17.9k
18
votes
5
answers
8k
views
Is $x^p-x+1$ always irreducible in $\mathbb F_p[x]$?
It seems that for any prime number $p$ and for any non-zero element $a$ in the finite field $\mathbb F_p$, the polynomial $x^p-x+a$ is irreducible over $\mathbb F_p$. (It is of course obvious that ...
- 17.9k
14
votes
3
answers
3k
views
Truncated Exponential Series Modulo $p$: Deeper meaning for a Putnam Question.
Apparently B6 of the Putnam this year asked:
Suppose $p$ is an odd prime. Prove that for $n\in \{0,1,2...p-1\}$, at least $\frac{p+1}{2}$ of the numbers $\sum^{p-1}_{k=0} k! n^{k}$ are not divisble ...
- 11.4k
14
votes
3
answers
1k
views
Probability of coprime polynomials
Given positive integer $N$, we choose $m_1, m_2, n_1, n_2$ independently and with equal probabilities from $\{0,1,\ldots,N\}$, and let
$f_1 = x^{m_1} + (1+x)^{n_1}$ and $f_2 = x^{m_2} + (1+x)^{n_2}$ ...
- 54.2k
12
votes
1
answer
273
views
Most points on a degree $p$ hypersurface?
Let $p$ be a prime. Let $f \in \mathbb{F}_p[x_1, \ldots, x_n]$ be a homogenous polynomial of degree $p$. Can $f$ have more than $(1-p^{-1}+p^{-2}) p^n$ zeroes in $\mathbb{F}_p^n$?
Basic observations: ...
- 156k
11
votes
1
answer
475
views
Greatest common divisor in $\mathbb{F}_p[T]$ with powers of linear polynomials
Let $n>1$ and $p$ be an odd prime with $p-1 \mid n-1$ such that $p^k - 1 \mid n-1$ does not hold for any $k>1$. Notice that, since $p-1 \mid n-1$, we have $T^p - T \mid T^n-T$ in $\mathbb{F}_p[T]...
- 63.1k
10
votes
1
answer
327
views
Proving that polynomials belonging to a certain family are reducible
In an article, I've found the following result. Unfortunately, it was derived from a general, somewhat complicated theory, that would be cumbersome for this result alone.
Assume that $\mathbb F_p$ is ...
- 687
9
votes
2
answers
766
views
What is a function field analog of Giuga's conjecture?
Giuga's conjecture (1950), which is still open and has strong numerical support, reads :
Let $n$ be a positive integer. If $1+\sum_{k=1}^{n-1}k^{n-1} \equiv 0\pmod{n}$ then $n$ is prime.
What would ...
- 2,901
8
votes
0
answers
140
views
Order of zeros for sparse polynomials mod $p$
It is a fairly well known fact that sparse polynomials $f(x)$ cannot have large order zeros other than at $x=0$. If $f(x)=a_1x^{r_1}+\cdots+a_kx^{r_k}$ then at $c
\neq 0$, $f$ has a zero of order at ...
- 671
7
votes
1
answer
1k
views
Roots of a polynomial in a finite field related to Fermat's Last Theorem
In my class, we proved the following condition: define the polynomial $P_l(x)$ as
$$P_l(x) = \sum_{r=1}^{l-1}{\frac{1}{r}x^{l-1-r}}$$
Then if for all $a \in \mathbb{Z}/l\mathbb{Z}-\{0,1\},$ $P_l(x)$...
- 495
7
votes
1
answer
1k
views
Polynomials which are functionally equivalent over finite fields
Recall that two polynomials over a finite field are not necessarily considered equal, even if they evaluate to the same value at every point. For example, suppose $f(x) = x^2 + x + 1$ and $g(x) = 1$. ...
- 1,703
6
votes
1
answer
331
views
Which criteria for "uniformly splitting" polynomials?
Let $P(x)$ be an irreducible monic polynomial of degree $\ge4$ with integer coefficients. We all know that over a finite field $\mathbb F_p$, $P$ will often split, and I am interested in polynomials ...
- 13.4k
6
votes
0
answers
253
views
Cardinality of a polynomial image $\pmod{p^n}$
Given $P(x) \in \mathbb{Z}[x]$ a polynomial, $n$ a positive integer and $p$ a prime, there is a result that relates $|\text{Im } P \pmod{p^n}|$ with $|\text{Im } P \pmod{p^{n+1}}|$ perhaps in terms of ...
- 61
5
votes
1
answer
2k
views
Irreducibility of some trinomials modulo $p$
Let $n>1$ be an integer. An old result of Selmer,
See Theorem 1, page 289 in
http://www.mscand.dk/article.php?id=1472,
(If the link does not work try googling: ...
- 1,641
5
votes
1
answer
629
views
How different can the bias of two polynomials be?
$\DeclareMathOperator\bias{bias}$I'm trying to figure out how to approach the following question:
Let $g$, $h$ be polynomials over $\mathbb{Z}_p$ (for prime $p$) with $n>1$ variables.
Denote by $\...
- 301
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
334
views
GCD in $\mathbb{F}_3[T]$ with powers of linear polynomials
This is a continuation of my previous question on $\gcd$s of polynomials of type $f^n - f$.
Let us call $n > 1$ simple at a prime $p$ when $p-1 \mid n-1$ but $p^k - 1 \not\mid n-1$ for all $k > ...
- 63.1k
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
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
4
votes
0
answers
134
views
$\delta$-equidistributed polynomials over finite fields
I'm trying to show that a polynomial over finite (prime) field is "close enough" to being equidistributed over its range. A polynomial $p(\cdot)$ from $\mathbb{F}^n$ to $\mathbb{F}$ is $\...
- 301
3
votes
0
answers
73
views
Is the discrete logarithm equivalent to solving polynomial discrete logarithms?
Suppose we can quickly solve the discrete logarithm modulo $p$. Let's say $2$ is a generator so we can quickly find $l$ for which $2^l =h$ for any given target $h$.
An interesting observation is that ...
- 591
3
votes
0
answers
174
views
Carlitz factorials and Euler-like series
Let $q$ be a power of a prime $p$. For every $i\in\mathbb N$, one denotes $D_i=\prod_{\substack{h\in\mathbb F_q[T]\text{ monic}\\\deg h=i}}\limits h$. For $n\in\mathbb N$, write $$n=n_0+n_1q+\cdots+...
- 3,998
2
votes
3
answers
6k
views
How to factorize X^n - 1 in Z/pZ?
How do I factorize a polynomial $X^n - 1$ over $\mathbb{F}_p$? In particular I need to find factors of the polynomial $X^{3^3 - 1} - 1 = X^{26} - 1$ over $\mathbb{F}_3$.
- 330
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
2
votes
0
answers
120
views
Looking at versions of Implicit Function Theorem (IFT) on rings
$ \let \ovr \overline
\def \Z {\mathbb Z}
\def \C {\mathbb C}
\def \F {\mathbb F}
\def \P {\mathcal P}
\def \x {\boldsymbol x}
\def \a {\boldsymbol a} $
Let $ \P = \{ p _ i ( \x , y ) \} _ { i = 1 } ^ ...
- 346
2
votes
0
answers
121
views
When $\gcd(P(x),Q(x))\bmod R(x)=\gcd(P(x) \bmod R(x),Q(x) \bmod R(x))$?
Let's $P,Q\in\mathbb K[x]$, with $\mathbb K$ a finite field.
On what necessary and sufficient condition on $R \in \mathbb K[x]$ is it :
$\gcd(P(x),Q(x))\bmod R(x)=\gcd(P(x) \bmod R(x),Q(x) \bmod R(x))...
- 4,074
2
votes
0
answers
114
views
Reducible polynomial among sequence of polynomials
Let $a_1$ and $a_2$ be two elements of a finte field $\mathbb{F}_{2^m}$ of even characteristic and $a_1^2\neq a_2$. Is it true that there always exists an element $a\in\{a_1,a_2,a_3,\ldots,a_{2^m}|a_{...
- 21
2
votes
0
answers
123
views
A special case of the polynomial Bézout's identity: bounding the co-factors
Let $F$ be a field of prime order $p$. Suppose that $f\in F[x]$ is a non-zero polynomial of degree $\deg f<p$. If $f$ does not have multiple roots, then there exist polynomials $P,Q\in F[x]$ such ...
- 550
2
votes
0
answers
95
views
Polynomials passing through points with tangential conditions
In corollary here http://math.mit.edu/~lguth/Exposition/erdossurvey.pdf on polynomial methods it is said "(Parameter counting) If $S\subset\mathbb F^n$ is a finite set, then there is a non-zero ...
- 13.9k
2
votes
0
answers
194
views
Number of common solutions of polynomial system
Let $ \mathbb{F}_p$ be a finite field and $\{f_j\}_{j=1}^{j=r} \subseteq \mathbb{F}_p[X_1,...,X_n]$ be a set of polynomials.
Let consider the system of equations:
$f_j(x_1,...,x_n)=0$ for $j = 1,......
- 2,576
1
vote
1
answer
139
views
A polynomial recovery problem
Suppose we know $deg(m(x))=n-1=deg(f_1(x))=deg(f_2(x))$.
Suppose we know $C_1(x),C_2(x)$ where $deg(C_i)=n$.
Then given $n$ values of $$C_1(x)(x+1)m(x) +C_1(x)(x+2)f_1(x)\in\Bbb F_q[x]$$ and $n$ ...
user94040
1
vote
0
answers
254
views
Reductions of a system of equations at various primes
Let $f_1, \dots, f_n$ be a finite set of polynomials in the polynomial ring $Z[x_1, \dots, x_m]$. At a prime $p$, let $N_p$ be the number of solutions $x=(x_1, \dots, x_m)\in (\mathbb{Z}/p\mathbb{Z})^...
- 685
1
vote
0
answers
189
views
Vanishing product of polynomials over finite fields
$(x_1-x_2-x_3+x_4)(x_2-x_4-x_3+x_1)(x_3-x_1)(x_4-x_2)\equiv 0$ over $\mathbb F_3$.
Take polynomials $p_1,\dots,p_n$ over variables $x_1,\dots,x_n$ such that $p_i$ does not depend on $x_i$ and $\Pi_{i=...
- 18.9k
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
0
votes
1
answer
195
views
Trying to solve for the remainder of $a^q$ modulo $q$
Let $q$ be a prime and $a$ be a number from $0$ to $q-1$ (not an equivalence class).
The elements $a^q$ are exactly the elements of order $q-1$ modulo $q^2$.
I'm trying to solve the equation:
$$a+2*\...
- 591