Waste less time on Facebook — follow Brilliant.
×

First CS's inequality

Prove/Disprove the following inequality.

\[ \sum_{cyc}\sum_{k=1}^{M}\phi(a_1^k)\geq\sum_{cyc}\sum_{k=1}^{M} \phi (a_1)^k\]

For all \(0\leq a_1 , a_2 , a_3 , ....., a_n \leq M\) and \(M\) is any natural number.

I have made the inequality more generalized.

Notation: \(\phi(\cdot) \) denotes the Euler's totient function.

You may also see Second CS's inequality

Note by Chinmay Sangawadekar
9 months, 1 week ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Not quite sure about this, correct me if I make a mistake somewhere.

Let \(p\) denotes an arbitrary prime number and let \(k,b \geq 1 \in \mathbb{N}\)

\(p^{k-1} \geq (p-1)^{k-1}\)

\(p^{-1} \geq p^{-k}(p-1)^{k-1}\)

\(p^{kb-1}(p-1) \geq p^{kb-k}(p-1)^{k}\)

\(p^{kb}-p^{kb-1} \geq {(p^{b}-p^{b-1})}^{k}\)

\(\phi(p^{kb}) \geq {\phi(p^{b})}^{k}\), noting that \(\phi(p^{n})=p^{n}-p^{n-1}\)

Let \(a={p_{1}}^{k_{1}}{p_{2}}^{k_{2}}\cdots{p_{n}}^{k_{n}}\).

From the result above, we have

\(\phi({p_{1}}^{kb_{1}})\phi({p_{2}}^{kb_{2}})\cdots\phi({p_{n}}^{kb_{n}}) \geq \phi{({p_{1}}^{b_{1}})}^{k}\phi{({p_{2}}^{b_{2}})}^{k}\cdots\phi{({p_{n}}^{b_{n}})}^{k}\)

\(\phi(a^{k}) \geq {\phi(a)}^{k}\)

Therefore, the inequality holds true, with equality holds only when \(a,b,c \in \{0,1\}\) or \(M=1\). Zk Lin · 9 months, 1 week ago

Log in to reply

Comment deleted 9 months ago

Log in to reply

@Chinmay Sangawadekar Done. Zk Lin · 9 months, 1 week ago

Log in to reply

@Zk Lin Nicely done ! I don't think that there will be any mistake...@ZK LIn Chinmay Sangawadekar · 9 months, 1 week ago

Log in to reply

@Chinmay Sangawadekar Thanks! Glad to know that. Zk Lin · 9 months, 1 week ago

Log in to reply

@Zk Lin Can't it be true for arbitary numbers ? Chinmay Sangawadekar · 9 months, 1 week ago

Log in to reply

@Chinmay Sangawadekar The inequality holds true for all numbers. What I meant was conditions for equality cases. Zk Lin · 9 months, 1 week ago

Log in to reply

@Zk Lin Oh , initially I proved this inequality for arbitary primes , Can this inequality have significance in problem solving or in any theorem proofs ? Chinmay Sangawadekar · 9 months, 1 week ago

Log in to reply

@Chinmay Sangawadekar Number theoretic inequalities are quite rare in math olympiads, so I guess it won't be that helpful? However, this is a nice result. I can imagine it being useful in theorem proofs, but I have not encountered enough number theory literature to see an application of this result yet. Zk Lin · 9 months, 1 week ago

Log in to reply

@Zk Lin @Otto Bretscher What is your opinion ? Chinmay Sangawadekar · 9 months, 1 week ago

Log in to reply

@Chinmay Sangawadekar Didn't we do this inequality in the first batch already, question 2?

It is good to know the equation \(\phi(n^k)=n^{k-1}\phi(n)\); this inequality is an immediate consequence. Otto Bretscher · 9 months, 1 week ago

Log in to reply

Comment deleted 9 months ago

Log in to reply

@Chinmay Sangawadekar As you know, there is a big difference between Olympiad problems and "real mathematics". In hundreds of seminar talks I have attended at many universities, where people present their research papers, I have never heard anybody talk about number theoretical inequalities (or inequalities in general). Otto Bretscher · 9 months, 1 week ago

Log in to reply

@Otto Bretscher So you mean this is something new ? @Otto Bretscher Chinmay Sangawadekar · 9 months, 1 week ago

Log in to reply

@Otto Bretscher Do you think that such inequalities will be useful for ay theorem proofs or problems ? @Otto Bretscher Chinmay Sangawadekar · 9 months, 1 week ago

Log in to reply

Comment deleted 9 months ago

Log in to reply

@Chinmay Sangawadekar Sure, why not? Zk Lin · 9 months, 1 week ago

Log in to reply

For \(k>1\),

\[\phi(a^k)=a^{k-1}\phi(a)\]

Since

\[\phi(a)<a\]

\[\phi(a)^k<a^{k-1} \phi(a)=\phi(a^k)\]

For k=1, the result \(\phi(a^k)=\phi(a)\) is trivial.

The result above follows. Julian Poon · 8 months, 3 weeks ago

Log in to reply

@Julian Poon Exactly ! :) Chinmay Sangawadekar · 8 months, 3 weeks ago

Log in to reply

Comment deleted 9 months ago

Log in to reply

@Chinmay Sangawadekar Bro, I see that you have studied all these awesome stuffs!

Can you please suggest me resources for studying them?Thanks!

(I mean modular arithmetic) Harsh Shrivastava · 9 months, 1 week ago

Log in to reply

@Harsh Shrivastava You can see that the inequality is proved , I had proved this only for arbitary peimes , and I am searching a more general proof , as you xan see the generalized inequality ... I will be glad to hear your opinions related to this new NT inequality.. @Harsh Shrivastava Chinmay Sangawadekar · 9 months, 1 week ago

Log in to reply

@Chinmay Sangawadekar I will try this in a few days,sorry a bit busy with board stuffs. Harsh Shrivastava · 9 months, 1 week ago

Log in to reply

@Harsh Shrivastava You may start up with Elementary Number Theory by David Burton , and for advanced , you may refer Advanced Number Theory .... How can I become good at inequalities ? Please suggest ..... Chinmay Sangawadekar · 9 months, 1 week ago

Log in to reply

@Chinmay Sangawadekar I am not good in inequalities.

People like @ZK LIn @MS HT @gurido cuong are real inequality gods.

Please suggest us how to become good at inequalities ?

Thnx! Harsh Shrivastava · 9 months, 1 week ago

Log in to reply

@Harsh Shrivastava You are too generous with your compliment. I am definitely nowhere near the levels of @MS HT and @Gurido Cuong. They post new inequality problems at a rate faster than I can solve them, and I am nowhere near the level of a 'god' either.

However, since you ask for advice, I will do my best to provide them.The "advice" below comes from my personal experience and might not work for everyone, so take it with a pinch of salt.

I initially start studying inequalities seriously from the excellent note Mildorf "Olympiad Inequalities", which I believe is available somewhere on the web (AoPS maybe?). You might find that helpful.

A more elementary version of this is Siamin Riasat "Basics in Olympiad Inequalities". When I am a complete newbie, I rely on it heavily and tried (unsuccessfully) to solve all the problems. Easy as the questions are, they provide a good chance for you to apply the inequalities introduced. Zk Lin · 9 months, 1 week ago

Log in to reply

@Harsh Shrivastava I'm not good as you think.Because I'm not better than many people in my school or my social... Ms Ht · 9 months, 1 week ago

Log in to reply

@Harsh Shrivastava Here Mehul Arora · 9 months, 1 week ago

Log in to reply

@Mehul Arora I can't help but notice that i am a member of that site.

BTW your joke was awesome.I am rolling over floor laughing.I appreciate efforts that you put in making this joke.You must consider a career as a stand-up comedian.Hats off to you! Harsh Shrivastava · 9 months, 1 week ago

Log in to reply

@Harsh Shrivastava I like your sense of sarcasm :3 Preserve it, not many have that. Mehul Arora · 9 months, 1 week ago

Log in to reply

@Mehul Arora LOL! :3 :3 :3 Nihar Mahajan · 9 months, 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...