Putnam 2015 A3

The post below has been deleted. Click to close.

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

Kent Merryfield

18574 posts

Kent Merryfield

#1 h Dec 6, 2015, 10:12 PM • 4 Y

Y by opptoinfinity, Davi-8191, Adventure10, Mango247

Compute $\log_2\left(\prod_{a=1}^{2015}\prod_{b=1}^{2015}\left(1+e^{2\pi iab/2015}\right)\right)$ Here $i$ is the imaginary unit (that is, $i^2=-1$ ).

Z K Y

The post below has been deleted. Click to close.

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

Kent Merryfield

18574 posts

Kent Merryfield

#2 h Dec 6, 2015, 10:15 PM • 4 Y

Y by v_Enhance, Adventure10, Mango247, Dhruv777

The value of that logarithm is $13725.$

Let $n>1$ be an odd integer, and let $\zeta = e^{2\pi i/n}.$ Then the numbers $1+\zeta^k$ for $1\le k\le n$ are the $n$ roots of the polynomial $(z-1)^n=1.$ Multiplied out, that is $z^n - \cdots -2=0.$ The product of the roots is $2.$

If $a$ is relatively prime to $n$ , then the numbers $\zeta^{ab}$ for $1\le b\le n$ encompass all $n$ of possible powers of $\zeta,$ and hence $\prod_{b=1}^n(1+\zeta^{ab})=2.$

But if $\gcd(a,n)=k>1,$ that means that $a=jk,$ with $k\mid n$ and $j$ relatively prime to $n/k.$ In that case, the powers $\zeta^{ab}$ can be written as $(\zeta^{k})^{jb}.$ We have that the numbers $(1+(\zeta^k)^{jb})$ are the roots of $(z-1)^{n/k}=1,$ listed $k$ times each. That means that $\prod_{b=1}^n(1+\zeta^{ab})=2^k.$

To assemble our answer, we note that $2015=5\cdot 13\cdot 31.$ In each line below, the ``inside product" is $\prod_{b=1}^n(1+\zeta^{ab}).$

$a$ relatively prime to $2015.$ Inside product is $2,$ and this happens $\phi(2015)=1440$ times.

$a=5j,$ $j$ relatively prime to $403.$ Inside product is $2^5,$ happens $\phi(403)=360$ times.

$a=13j,$ $j$ relatively prime to $155.$ Inside product is $2^{13},$ happens $\phi(155)=120$ times.

$a=31j,$ $j$ relatively prime to $65.$ Inside product is $2^{31},$ happens $\phi(65)=48$ times.

$a=65j,$ $j$ relatively prime to $31.$ Inside product is $2^{65},$ happens $\phi(31)=30$ times.

$a=155j,$ $j$ relatively prime to $13.$ Inside product is $2^{155},$ happens $\phi(13)=12$ times.

$a=403j,$ $j$ relatively prime to $5.$ Inside product is $2^{403},$ happens $\phi(5)=4$ times.

$a=2015.$ Inside product is $2^{2015}.$ Happens once.

Multiply all of these together and take the base 2 logarithm (meaning we add the exponents). The result is $1440\cdot 1+360\cdot 5+120\cdot 13+48\cdot 31+30\cdot 65+12\cdot 155+4\cdot 403+1\cdot 2015 = 13725.$

This post has been edited 1 time. Last edited by Kent Merryfield, Dec 8, 2015, 2:48 PM

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6877 posts

v_Enhance

#3 h Dec 6, 2015, 10:17 PM • 12 Y

Y by Kent Merryfield, GreenKeeper, rkm0959, CeuAzul, rafayaashary1, Laindingoldlee, Aryan-23, XbenX, Gaussian_cyber, inoxb198, Adventure10, Mango247

You can evaluate the last part with a trick. For completeness, full solution below:

First, we use the fact that for any odd integer $m$ , we have
$\prod_{1 \le b \le m} (1 + \zeta^b) = 2$ where $\zeta$ is an $m$ th root of unity. (Just plug $-1$ into $X^m-1$ .) Thus
$\begin{align*} \log_2 \prod_{a=1}^{2015} \prod_{b=1}^{2015} \left( 1 + e^{\frac{2\pi i a b}{2015}} \right) &= \log_2 \prod_{a=1}^{2015} 2^{\gcd(a,2015)} \\ &= \sum_{a=1}^{2015} \gcd(a,2015) \\ &= \sum_{d \mid 2015} \frac{2015}{d} \phi(d) \\ &= (5+\phi(5))(13+\phi(13))(31+\phi(31)) \\ &= 9 \cdot 25 \cdot 61 \\ &= 13725. \end{align*}$

Z K Y

The post below has been deleted. Click to close.

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

BOGTRO

5818 posts

BOGTRO

#4 h Dec 6, 2015, 10:17 PM • 2 Y

Y by Adventure10, Mango247

Sol

Z K Y

The post below has been deleted. Click to close.

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

hoeij

35 posts

hoeij

#5 h Dec 6, 2015, 10:44 PM • 3 Y

Y by Adventure10, Mango247, KnowingAnt

Notice that the function $f(n) := \sum_{a=1}^n {\rm gcd}(a,n)$ is also a multiplicative function. So $f(2015) = f(5) f(13) f(31)$ .

This post has been edited 1 time. Last edited by hoeij, Dec 7, 2015, 2:57 PM
Reason: Replaced plain text by LaTeX

Z K Y

The post below has been deleted. Click to close.

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

pi37

2079 posts

pi37

#6 h Dec 6, 2015, 11:02 PM • 3 Y

Y by rafayaashary1, Adventure10, Mango247

Sketch:
Let
$F(x)=\prod_{1\le a,b\le 2015} (x-\omega^{ab})$ where $\omega$ is a primitive $2015$ th root of unity. We want to find $\log_2\left(-F(-1)\right)$ . Then we can write (after checking some symmetry thing)
$F(x)=\prod_{d\mid 2015} \Phi_d(x)^{h(d)}$ for some $h$ mapping from the divisors of $2015$ to $\mathbb{Z}_{\ge 0}$ . But $\Phi_{d}(-1)=1$ unless $d=1$ for $d\mid 2015$ , so it suffices to find $h(1)$ . This is the number of pairs $(a,b)$ with $2015\mid ab$ , which is easily computed to be $(2\cdot 5-1)(2\cdot 13-1)(2\cdot 31-1)=13725$ . Thus our answer is
$\log_2\left(-(-2)^{13725}\right)=13725$ Also, it took a lot longer than it should have to realize $403$ is not prime...

This post has been edited 1 time. Last edited by pi37, Dec 6, 2015, 11:02 PM

Z K Y

The post below has been deleted. Click to close.

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

Naysh

2134 posts

Naysh

#7 h Dec 6, 2015, 11:32 PM • 3 Y

Y by KarlMahlburg, Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

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

jh235

910 posts

jh235

#8 h Dec 7, 2015, 12:33 AM • 2 Y

Y by Adventure10, Mango247

I lot of people at the location I was at just did $e^{\frac{2\pi i}{2015}ab}=\left(e^{2\pi i}\right)^{\frac{ab}{2015}}=1^{\frac{ab}{2015}}=1\Rightarrow$ the answer is $2015^2$ . I am guessing that this ended up being a common mistake for those unfamiliar with complex numbers.

This post has been edited 2 times. Last edited by jh235, Dec 7, 2015, 12:35 AM

Z K Y

The post below has been deleted. Click to close.

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

AnderExtrema

417 posts

AnderExtrema

#9 h Dec 7, 2015, 1:04 AM • 2 Y

Y by Adventure10, Mango247

jh235 wrote:

I lot of people at the location I was at just did $e^{\frac{2\pi i}{2015}ab}=\left(e^{2\pi i}\right)^{\frac{ab}{2015}}=1^{\frac{ab}{2015}}=1\Rightarrow$ the answer is $2015^2$ .

What is actually wrong with the logic you just stated? I didn't think to do that on the exam, but looking at it I can't see why it's wrong.

Z K Y

The post below has been deleted. Click to close.

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

djmathman

7938 posts

djmathman

#10 h Dec 7, 2015, 1:10 AM • 3 Y

Y by AnderExtrema, Adventure10, Mango247

First off, you're looking at $1+\omega^{ab}$ , not $\omega^{ab}$ , and distributive laws don't really hold for exponents

On a similar vein, one may ask why the product of each of the $2015$ terms formed when $a$ is fixed is not simply $2$ . The basic problem with this is that the idea of the product being equal to $2$ relies on the fact that the each of the roots of unity is hit exactly once. That doesn't occur whenever $\gcd(n,2015)>1$ . For example, if $n=5$ , the product will cover $\omega^5$ , $\omega^{10}$ , $\ldots$ , $\omega^{2015}$ , then the sequence will repeat four more times. Each of these can be considered a primitive $403^{\text{rd}}$ root of unity, so together their product (of just these 403 terms) is 2. This means that for $n=5$ the result is $2^5$ .

This post has been edited 2 times. Last edited by djmathman, Dec 7, 2015, 1:13 AM

Z K Y

The post below has been deleted. Click to close.

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

Kent Merryfield

18574 posts

Kent Merryfield

#11 h Dec 7, 2015, 2:55 AM • 3 Y

Y by v_Enhance, Adventure10, Mango247

v_Enhance wrote:

You can evaluate the last part with a trick.

Thanks, v_Enhance. I knew all along that this was a convolution of multiplicative functions. I didn't have the patience to figure out which functions were involved and what their convolution was. And I paid a price for it: the number that I wrote down while proctoring was incorrect due to an arithmetic error. I only fixed it later that night when I started writing up solutions in $\LaTeX$ in anticipation of posting them.

Z K Y

The post below has been deleted. Click to close.

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

Kent Merryfield

18574 posts

Kent Merryfield

#12 h Dec 7, 2015, 7:36 PM • 4 Y

Y by GreenKeeper, Naysh, v_Enhance, Adventure10

Just so I have this written down somewhere, I want to make all of this more explicit. This has all been said by various posters above; I'm just collecting it in one place.

In number theory, a multiplicative function is a function $g$ whose domain is $\mathbb{N}$ such that $g(ab)=g(a)g(b)$ whenever $a$ and $b$ are relatively prime. A multiplicative function is determined by its values on prime powers.

Given two multiplicative functions, we may compute their convolution: $f*g(n)=\sum_{d\mid n}f(d)g\left(\frac nd\right).$ We can show that $f*g$ is multiplicative whenever $f$ and $g$ are multiplicative.

The identity function $\mathrm{id}(n)=n$ and the Euler totient function $\phi(n)$ are both multiplicative functions. They are determined on prime powers by $\mathrm{id}(p^k)=p^k$ and $\phi(p^k)=p^{k-1}(p-1).$

Let $f(n)=\log_2\left(\prod_{a=1}^n\prod_{b=1}^n(1+e^{2\pi i ab/n})\right).$

By several different posters' arguments above (including mine), $f=\mathrm{id}*\phi.$ Since $f$ is given by a convolution of multiplicative functions, $f$ is multiplicative. Therefore it is determined by its values at prime powers. $\begin{align*}f(p^k)&=\sum_{j=0}^{k}p^j\phi(p^{k-j})\\ &=\sum_{j=0}^{k-1}p^jp^{k-j-1}(p-1)+p^k\\ &=kp^{k-1}(p-1)+p^k=p^{k-1}(kp-k+p)\end{align*}$ Particularized to $k=1,$ we have $f(p)=2p-1,$ and that's all we needed for this particular problem.
$f(2015)=f(5)f(13)f(31)=9\cdot 25\cdot 61=13725.$ There is a transform appropriate to this: Dirichlet series.
If $f$ is multiplicative define $F(s)=\sum_{n=1}^{\infty}\frac{f(n)}{n^s},$ for sufficiently large $s.$

If $h=f*g,$ then $H(s)=F(s)G(s).$

The Dirichlet series associated to $\mathrm{id}$ is $\zeta(s-1)$ and the Dirichlet series associated to $\phi$ is $\frac{\zeta(s-1)}{\zeta(s)}.$ Hence for the function $f$ in this problem, $F(s)=\frac{\left(\zeta(s-1)\right)^2}{\zeta(s)}.$

This post has been edited 1 time. Last edited by Kent Merryfield, Dec 7, 2015, 7:49 PM
Reason: Spelling

Z K Y

The post below has been deleted. Click to close.

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

themorninglighttt

789 posts

themorninglighttt

#13 h Dec 8, 2015, 6:22 AM • 2 Y

Y by Adventure10, Mango247

How many points off would it be if I did my calculation wrong, but I had everything else right?

Z K Y

The post below has been deleted. Click to close.

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

Kent Merryfield

18574 posts

Kent Merryfield

#14 h Dec 11, 2015, 1:04 AM • 2 Y

Y by Adventure10, Mango247

Correction:

The "multiplicative function" $f(n)$ is $\mathrm{id}*\phi(n)$ for $n$ odd, but it is undefined for $n$ even. We could make a multiplicative function by defining it to be zero for $n$ even, but if we do that, those Dirichlet series I claimed above will need to be recalculated.

Z K Y

The post below has been deleted. Click to close.

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

mathocean97

606 posts

mathocean97

#15 h Dec 11, 2015, 2:25 AM • 2 Y

Y by Adventure10, Mango247

Are you sure? I'm pretty sure it is multiplicative everywhere.

Z K Y

The post below has been deleted. Click to close.

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

adityaguharoy

4655 posts

adityaguharoy

#16 h Dec 14, 2015, 3:21 AM • 2 Y

Y by Adventure10, Mango247

yes it is multiplicative

Z K Y

The post below has been deleted. Click to close.

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

adityaguharoy

4655 posts

adityaguharoy

#17 h Dec 14, 2015, 3:21 AM • 2 Y

Y by Adventure10, Mango247

yes multiplicative...

Z K Y

The post below has been deleted. Click to close.

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

AnderExtrema

417 posts

AnderExtrema

#18 h Dec 14, 2015, 3:24 AM • 1 Y

Y by Adventure10

I thought you learned what the edit function was. (My tone is not even sarcastic, more so just questioning.)

Z K Y

The post below has been deleted. Click to close.

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

Kent Merryfield

18574 posts

Kent Merryfield

#19 h Dec 14, 2015, 4:45 AM • 2 Y

Y by Adventure10, Mango247

No, the problem with $f(n)$ as defined in my post #12 above is that it is not defined for $n$ even. A multiplicative function is supposed to be defined on $\mathbb{N}.$

If $n$ is even, then $\prod_{j=1}^n(1+e^{2\pi ij/n})=0.$ With that factor in there, the whole double product is zero, which makes its logarithm undefined.

As I said, we could make a multiplicative function by defining $f(2)=0$ and therefore $f(n)=0$ for all even $n.$

Z K Y

The post below has been deleted. Click to close.

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

adityaguharoy

4655 posts

adityaguharoy

#20 h Dec 15, 2015, 4:33 PM • 2 Y

Y by Adventure10, Mango247

yes precisely that

Z K Y

The post below has been deleted. Click to close.

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

UrInvalid

627 posts

UrInvalid

#21 h Sep 9, 2017, 6:15 AM • 2 Y

Y by Adventure10, Mango247

So I just mocked this, and I have a question:
How many points would one get for explaining the roots thing, finding the correct final sum, and then adding wrong? (like, my solution is almost identical to post #2, but i messed up in the tens place)

Z K Y

The post below has been deleted. Click to close.

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

jmerry

12096 posts

jmerry

#22 h Sep 9, 2017, 6:42 AM • 1 Y

Y by Adventure10

The standard response: Putnam grading is opaque. No commentary on it is ever released, and the individual scores you get back through your sponsor at the school aren't broken down by problem.

That said, a simple arithmetic error like that should be a $10^-$ , not a $0^+$ . (All scores on problems are in the 0 to 2 range or the 8 to 10 range)

Z K Y

The post below has been deleted. Click to close.

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

UrInvalid

627 posts

UrInvalid

#23 h Sep 9, 2017, 4:32 PM • 2 Y

Y by Adventure10, Mango247

jmerry wrote:

The standard response: Putnam grading is opaque. No commentary on it is ever released, and the individual scores you get back through your sponsor at the school aren't broken down by problem.

That said, a simple arithmetic error like that should be a $10^-$ , not a $0^+$ . (All scores on problems are in the 0 to 2 range or the 8 to 10 range)

Cool, thank you.

Z K Y

The post below has been deleted. Click to close.

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

sqing

41911 posts

sqing

#24 h Jul 27, 2019, 8:40 AM • 1 Y

Y by Adventure10

https://artofproblemsolving.com/community/c6h1883358p12823215:
Compute $\log_2\left(\prod_{a=0}^{2018}\prod_{b=0}^{2018}\left(1+e^{\frac{2\pi iab}{2019}}\right)\right)$ Here $i$ is the imaginary unit (that is, $i^2=-1$ ).

Z K Y

The post below has been deleted. Click to close.

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

Chimphechunu

233 posts

Chimphechunu

#25 h Jul 27, 2019, 8:53 AM • 2 Y

Y by Adventure10, Mango247

What is the j here?

Z K Y

The post below has been deleted. Click to close.

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

sixoneeight

1138 posts

sixoneeight

#26 h Jan 10, 2024, 4:53 AM

Y by

For a fixed $a$ , let $d = \gcd(a, 2015)$ . Then, the inner product contains the $\frac{2015}{d}$ -th roots of unity, each occurring $d$ times. Specifically, let
$P_n(x) = x^n-1=\prod_{c=0}^{n-1}\left(x-e^{2\pi ic/n}\right)$ be a monic polynomial with $n$ roots being the $n$ -th roots of unity. Then,
$\prod_{b=1}^{2015}\left(1+e^{2\pi i ab/2015}\right) = (-1)^{2015}\left(P_{\frac{2015}{d}}(-1)\right)^{d}=2^{d}$ Thus, the entire expression is simply
$\sum_{a=1}^{\infty}\gcd(a,2015) = (1+1+1+1+5)(1+1+\dots+1+13)(1+1+\dots+1+31)$ because we have a factor of $5$ every $5$ terms and a factor of $1$ otherwise, etc. We can evaluate the answer as $\boxed{13725}$ .

Z K Y

The post below has been deleted. Click to close.

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

lifeismathematics

1188 posts

lifeismathematics

#27 h Apr 23, 2024, 2:50 PM • 1 Y

Y by Sagnik123Biswas

cosnider $\zeta:=e^{\frac{2i\pi}{n}}$ then $\zeta^{k}=\zeta_{k}$ are roots of the equation $x^{n}-1$ $\forall$ $0 \leqslant k \leqslant n-1$

We notice , $\prod_{i=1}^{n}(1+\zeta_{i})=2$ for odd $n$ .

Noticing the fact that if , $\gcd(a,n)=1$ then the set $\mathcal{S}=\{0,a,2a,\cdots, (n-1)a\} \equiv \{0,1,\cdots , n-1\} \pmod{n}$

So , $\prod_{b=1}^{n} \left(1+e^{\frac{i2\pi ab}{n}}\right)=2$ whenever $\gcd(a,n)=1$ .

Now consider $\gcd(a,n):=d$ , then $\prod_{b=1}^{\frac{2015}{d}} \displaystyle \left(1+e^{\frac{i2\pi \frac{a}{d}\cdot b}{\frac{n}{d}}}\right)=2$ ( Since $\gcd(\frac{n}{d} , \frac{a}{d})=1$ ).

so , $\prod_{b=1}^{b=n} \left(1+e^{\frac{i2\pi ab}{n}}\right)=2^{d}$ , hence $\left(\prod_{a=1}^{2015}\prod_{b=1}^{2015}\left(1+e^{2\pi iab/2015}\right)\right)=\log_{2}\left(\prod_{a=1}^{n} 2^{\gcd(a,n)}\right)=\log_{2}\left(2^{\sum_{a=1}^{n} \gcd(a,n)}\right)=\sum_{a=1}^{n} \gcd(a,n)$
.

for $n=2015$ it is just nothing but $(5+\phi(5))(13+\phi(13))(31+\phi(30))=\boxed{13725}$ . $\square$

This post has been edited 1 time. Last edited by lifeismathematics, Apr 23, 2024, 2:50 PM

Z K Y

The post below has been deleted. Click to close.

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

Mathandski

754 posts

Mathandski

#28 h Sep 4, 2024, 4:09 PM

Y by

$\text{[math]}$

Attachments:

Z K Y

The post below has been deleted. Click to close.

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

Sagnik123Biswas

420 posts

Sagnik123Biswas

#29 h Nov 28, 2024, 4:34 AM

Y by

We can simplify this as $\log_2{\prod_{i=1}^{n}2^{\gcd(i, 2015)}} = \sum_{i=1}^{2015}\gcd(i, 2015) = \sum_{d}\frac{2015}{d} \phi (d) = 2015(1 + \frac{4}{5})(1 + \frac{12}{13})(1 + \frac{30}{31}) = 13725$

Z K Y

The post below has been deleted. Click to close.

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

smileapple

1010 posts

smileapple

#30 h Feb 20, 2025, 8:43 PM

Y by

For simplicity set $\zeta=e^{2\pi i/2015}$ . Then note that $\zeta^a$ is a primitive $\frac{2015}d$ th root of unity where $d=\gcd(a,2015)$ , so that $\prod_{b=1}^{2015}(1+\zeta^{ab})=\left(\prod_{b=1}^{\frac{2015}{d}}(1+\zeta^{ab})\right)^{d}=((-1)^{\frac{2015}{d}}((-1)^{\frac{2015}{d}}-1))^{d}=2^d.$ Our desired value thus reduces to $\log_2\left(\prod_{a=1}^{2015} \prod_{b=1}^{2015} (1+\zeta^{ab})\right)=\sum_{a=1}^{2015}\gcd(a,2015)=\sum_{d\mid 2015}\varphi(d)\left(\frac{2015}d\right).$ Note that the product on the right hand side is a Dirichlet convolution and is therefore multiplicative. Since $2015=5\cdot13\cdot31$ , computation then yields an answer of $\boxed{13725}$ . $\blacksquare$

Z K Y