All Questions
17 questions with no upvoted or accepted answers
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
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
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
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
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
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.8k
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