Extension of $v_p$ to $\bar{\mathbb{Q}}$

by math154, Jul 10, 2011, 3:40 AM

Hmm this is pretty tricky and I wish I actually knew what it meant but here is an application anyway.

(Adapted from Gabriel Dospinescu, 2010 MR U160). Let $p$ be a prime and let $n,s$ be positive integers. Prove that
$v_p\left(\sum_{p|k,0\le k\le n}(-1)^{k} k^{s}\binom{n}{k}\right)\ge v_p(n!).$

Solution

Let the sum be $S$ . Then by a roots of unity filter and the Stirling number representation of $k^s$ (define $0^0=\binom{0}{0}=1$ ),

\[\begin{align*}
pS
&= \sum_{j=0}^{p-1}\sum_{k=0}^{n}\binom{n}{k} k^s (-\omega^j)^k \\
&= \sum_{j=0}^{p-1}\sum_{k=0}^{n}\binom{n}{k}(-\omega^j)^k\sum_{\ell=0}^{s}{s\brace\ell}\binom{k}{\ell}\ell! \\
&= \sum_{j=0}^{p-1}\sum_{\ell=0}^{\min(s,n)}{s\brace\ell}\ell!\sum_{k=0}^{n}\binom{k}{\ell}\binom{n}{k}(-\omega^j)^k \\
&= \sum_{j=0}^{p-1}\sum_{\ell=0}^{\min(s,n)}{s\brace\ell}\ell!\binom{n}{\ell}\sum_{k=\ell}^{n}\binom{n-\ell}{k-\ell}(-\omega^j)^k \\
&= \sum_{j=0}^{p-1}\sum_{\ell=0}^{\min(s,n)}{s\brace\ell}\ell!\binom{n}{\ell}(-\omega^j)^{\ell}(1-\omega^j)^{n-\ell}.
\end{align*}\]

If $j=0$ and $\ell<n$ , then we get a zero term. Also, if $s\ge n$ , then from the $\ell=n$ terms we get
$n!\sum_{j=0}^{p-1}(-\omega^j)^n=p n! (-1)^n [p|n],$ which is a multiple of $p^{1+v_p(n!)}$ . Thus it suffices to show that for $1\le j\le p-1$ ,
$v_p\left(\ell!\binom{n}{\ell}(1-\omega^j)^{n-\ell}\right)>v_p(n!)$ for all $0\le\ell\le\min(s,n-1)$ . But using the extension of $v_p$ to the field of algebraic numbers $\bar{\mathbb{Q}}$ (i.e. $v_p(x)=\frac{1}{d}v_p(f(0))$ , where $f$ is the minimal polynomial of $x$ ), the LHS is just
$v_p(n!)-\frac{n-\ell-s_p(n-\ell)}{p-1}+\frac{n-\ell}{p-1}>v_p(n!),$ so we're done (note that $n-\ell\ge1\implies s_p(n-\ell)>0$ in this case).

Edit: Two more applications (also from PFTB)!

(Gabriel Dospinescu). Let $p>2$ be a prime number and let $m$ and $n$ be multiples of $p$ , with $n$ odd. For any function $f:\{1,2,\ldots,m\}\to\{1,2,\ldots,n\}$ satisfying $\sum_{k=1}^{m}f(k)\equiv0\pmod{p}$ , consider the product $\prod_{k=1}^{m}f(k)$ . Prove that the sum of these products is divisible by $\left(\frac{n}{p}\right)^{m}$ . (Yes, we can strengthen it easily.)

(St. Petersburg 2003). Let $p$ be a prime and let $n\ge p$ and $a_1,a_2,\ldots,a_n$ be integers. Define $f_0=1$ and $f_k$ the number of subsets $B\subseteq\{1,2,\ldots,n\}$ having $k$ elements and such that $p$ divides $\sum_{i\in B}a_i$ . Show that $f_0-f_1+f_2-\cdots+(-1)^{n}f_n$ is a multiple of $p$ .

This post has been edited 8 times. Last edited by math154, Jan 17, 2013, 11:42 PM

p-adic valuation

sums

Comment

2 Comments

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

huh, that's pretty cool, not hard to prove, and seems really useful. Thanks.

It seems like it would make all problems about sums of combinations a lot easier to approach.

This post has been edited 1 time. Last edited by pythag011, Jul 10, 2011, 12:10 PM

by pythag011, Jul 10, 2011, 12:08 PM

Report

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

copied from comment [url=http://www.artofproblemsolving.com/blog/81602]here[/url] wrote:

PFTB doesn't actually teach valuations explicitly, but SFTB does in the algebraic NT chapter (based on this, which solves one of the later problems in the original PFTB chapter). Actually I guess I'll write out the problem:

Quote:

Let $a_1,a_2,\ldots,a_n$ be complex numbers such that $a_1^m+a_2^m+\cdots+a_n^m$ is an integer for all positive integers $m$ . Prove that $(x-a_1)(x-a_2)\cdots(x-a_n)\in\mathbb{Z}[x]$ .

BTW, take the definition of $v_p$ with a grain of salt; I just copied it from U160 here and I have a feeling harazi might not have been too careful/precise writing it. I think in this specific case it's easier to rephrase it as " $p^{-1/(p-1)}(1-z)$ is an invertible algebraic integer for primitive $p$ th roots of unity $z$ " (to prove it, note that $\frac{1-z^j}{1-z}$ is an invertible algebraic integer for all $j$ relatively prime to $p$ ). I asked Aaron Pixton at MOP this year if that definition was correct and he said you need to look at the minimal polynomial $f$ in the field $\mathbb{Q}_p$ of $p$ -adic numbers rather than just $\mathbb{Q}$ for it to work. So here it's the same but in general probably not; also this was in a rather informal setting (the class was about Newton polygons as applied to $\mathbb{F}_p[x]$ irreducibility) so he might've left out some details.

by math154, Jan 18, 2013, 6:24 PM

Report

Submit

!!!!!!!!
by stroller, Mar 10, 2020, 8:15 PM
cooooooool
nice blog
by Navansh, Jun 4, 2019, 7:47 AM
Victor is one of the GOATs.
by awesomemathlete, Oct 2, 2018, 11:48 PM
This blog is truly amazing.
by sunfishho, Feb 20, 2018, 6:32 AM
what a gem.
by vjdjmathaddict, May 10, 2017, 3:26 PM
Advertisement
by ahaanomegas, Dec 15, 2013, 7:21 PM
yo dawg i heard you imo
by Mewto55555, Aug 1, 2013, 10:25 PM
Good job on 5 problems on USAMO. I know that is a pretty bad score for someone as awesome as you on a normal USAMO, but no one got all 6 this year so it's GREAT!

VICTOR WANG 42 ON IMO 2013 LET'S GO.

See you at MOP this year (probably ).
by yugrey, May 3, 2013, 10:32 PM
you can just write "Solution
" instead of "Click to reveal hidden text
"

by math154, Feb 6, 2013, 6:33 PM
Hello. May I ask a stupid question: how to turn "Hidden Text" into hidden "Solution" tag?
by ysymyth, Feb 1, 2013, 12:59 PM
This is a good blog.I like it.
by Lingqiao, Jul 17, 2012, 4:21 PM
hi.i like the blog.
by Dranzer, Feb 9, 2012, 12:25 PM
sorry, i've decided this blog is just for the random stuff i do. don't take it personally... you can always post things on your own blog
by math154, Nov 23, 2011, 10:26 PM
what i got uncontribbed for posting a nice geo problem?
by yugrey, Nov 23, 2011, 1:32 AM
Can I be a contributor?
by Binomial-theorem, Oct 5, 2011, 12:39 AM
by gauss1181, Mar 8, 2009, 5:09 PM
i hate you
by alsyy, Mar 8, 2009, 4:37 PM
Fine. I don't care.
by math154, Mar 8, 2009, 1:34 AM
Math154: It was West Somethign Middle School from Columbia that got 2nd.
by Mewto55555, Mar 8, 2009, 1:20 AM
Oh dang, I already feel like deleting this blog. Maybe I should not do that for a while, though.
by math154, Mar 6, 2009, 2:50 AM
math154 mew and tinytim tied for first at chapter...
by AIME15, Mar 6, 2009, 1:06 AM
Thanks! Good luck to you too.
by math154, Mar 5, 2009, 1:00 AM
good luck on saturday
by gauss1181, Mar 5, 2009, 12:51 AM
Yeah gauss, our chapter sends the top 50 individuals and the top 10 teams.
by math154, Mar 4, 2009, 10:49 PM
Me wants be contrib.
by AIME15, Mar 4, 2009, 5:07 PM
I'll contrib in the future when I feel like it. I'm not gonna forget you, though, so don't worry.
by math154, Mar 2, 2009, 11:55 PM
third! contrib?
by nikeballa96, Mar 2, 2009, 10:40 PM
2nd Shout!
by gauss1181, Feb 28, 2009, 5:25 PM
1st Shout!
by mathemagician1729, Feb 28, 2009, 4:02 AM

101 shouts

I guess this is a blog

Extension of $v_p$ to $\bar{\mathbb{Q}}$

by math154, Jul 10, 2011, 3:40 AM

2 Comments