• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 19:16
CEST 01:16
KST 08:16
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Code S Season 2 - RO4 & Finals Results (2025)0Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0TL Team Map Contest #5: Presented by Monster Energy4Code S RO8 Preview: herO, Zoun, Bunny, Classic7Code S RO8 Preview: Rogue, GuMiho, Solar, Maru3
Community News
Weekly Cups (June 9-15): herO doubles on GSL week0Firefly suspended by EWC, replaced by Lancer8Classic & herO RO8 Interviews: "I think it’s time to teach [Rogue] a lesson."2Rogue & GuMiho RO8 interviews: "Lifting that trophy would be a testament to all I’ve had to overcome over the years and how far I’ve come on this journey.8Code S RO8 Results + RO4 Bracket (2025 Season 2)14
StarCraft 2
General
How herO can make history in the Code S S2 finals Firefly suspended by EWC, replaced by Lancer Rain's Behind the Scenes Storytime Code S Season 2 - RO4 & Finals Results (2025) Weekly Cups (June 9-15): herO doubles on GSL week
Tourneys
$3,500 WardiTV European League 2025 RSL: Revival, a new crowdfunded tournament series [GSL 2025] Code S: Season 2 - Semi Finals & Finals WardiTV Mondays Sparkling Tuna Cup - Weekly Open Tournament
Strategy
Simple Questions Simple Answers [G] Darkgrid Layout
Custom Maps
[UMS] Zillion Zerglings
External Content
Mutation # 478 Instant Karma Mutation # 477 Slow and Steady Mutation # 476 Charnel House Mutation # 475 Hard Target
Brood War
General
BGH Auto Balance -> http://bghmmr.eu/ ASL20 Preliminary Maps BW General Discussion Recent recommended BW games FlaSh Witnesses SCV Pull Off the Impossible vs Shu
Tourneys
[Megathread] Daily Proleagues [BSL 2v2] ProLeague Season 3 - Friday 21:00 CET Small VOD Thread 2.0 [BSL20] ProLeague Bracket Stage - Day 4
Strategy
I am doing this better than progamers do. [G] How to get started on ladder as a new Z player
Other Games
General Games
Stormgate/Frost Giant Megathread Nintendo Switch Thread Path of Exile Beyond All Reason What do you want from future RTS games?
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
Vanilla Mini Mafia TL Mafia Community Thread
Community
General
US Politics Mega-thread Things Aren’t Peaceful in Palestine Echoes of Revolution and Separation UK Politics Mega-thread Russo-Ukrainian War Thread
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Korean Music Discussion [Manga] One Piece
Sports
2024 - 2025 Football Thread Formula 1 Discussion NHL Playoffs 2024 TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List
Blogs
A Better Routine For Progame…
TrAiDoS
StarCraft improvement
iopq
Heero Yuy & the Tax…
KrillinFromwales
I was completely wrong ab…
jameswatts
Need Your Help/Advice
Glider
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 32527 users

Math Puzzle #3

Blogs > mieda
Post a Reply
1 2 3 Next All
mieda
Profile Blog Joined February 2010
United States85 Posts
Last Edited: 2010-09-12 22:32:52
September 10 2010 20:12 GMT
#1
Let f,g be polynomials with rational coefficients. Suppose f(Q) = g(Q) (i.e. the sets of values of f and g on the rationals are the same). Then f(x) = g(ax + b) for some rational constants a,b.

Remark. It generalizes to number fields with real embeddings.

Note that the converse is trivial.

Solution

The idea is that (mod the full details) there's a fixed discrete subgroup L of Q such that for any integer x, the rational solutions, viewed in y, of g(y) = f(x) are all in L. To extract the behavior of y as x varies, and compare the coefficients at the same time, i.e. the growth rates, you can consider expressions of the form g(y') - g(y) = f(x+1) - f(x) where y' is the corresponding rational number such that g(y') = f(x+1). By mean value theorem (don't quite need this, since f,g are polynomials so one can potentially do all the computations by algebra) the expression extracts out y' - y in terms of f'(x) and g'(y) roughly, and this gives a good comparison of y as x varies. This is the idea, and I do some computations to show that this works.

Also, simple valuation calculations (plug in this, plug in that rational number, compare the p-adic valuations) don't really seem to get anywhere, as I give plenty of counter examples and point out the problems to the claims of one of the posters below.

*
Assault_1
Profile Joined April 2009
Canada1950 Posts
September 10 2010 20:34 GMT
#2
so whats the question?
mieda
Profile Blog Joined February 2010
United States85 Posts
September 10 2010 20:43 GMT
#3
On September 11 2010 05:34 Assault_1 wrote:
so whats the question?


Proving it.
Piege
Profile Joined October 2009
United Kingdom128 Posts
September 10 2010 20:52 GMT
#4
Would a non-math major/non-math enthusiast be able to solve this?
Never_V_ -> Fin
category
Profile Joined July 2009
United States85 Posts
September 10 2010 20:53 GMT
#5
the sets f(Q) and g(Q) are not counting multiplicity right?
category
Profile Joined July 2009
United States85 Posts
September 10 2010 20:54 GMT
#6
On September 11 2010 05:52 Piege wrote:
Would a non-math major/non-math enthusiast be able to solve this?


I don't know the solution yet but I suspect the answer to your question is no.
mieda
Profile Blog Joined February 2010
United States85 Posts
Last Edited: 2010-09-10 20:56:54
September 10 2010 20:55 GMT
#7
On September 11 2010 05:53 category wrote:
the sets f(Q) and g(Q) are not counting multiplicity right?


They're just sets, not really any structures on them (for ex. ramifications). For example for the functio f(x) = x^2 the set f(Q) is just the set of all squares of rational numbers. We don't care that f(x) = 0 ramifies (and elsewhere unramifies). It's just a naive set.

I wonder if that's what you meant. So yes, I think we're not counting multiplicities here, whatever you mean by that in this context. f(Q) = {y : y = f(a) for some rational a}.
category
Profile Joined July 2009
United States85 Posts
September 10 2010 20:59 GMT
#8
lol. I don't know about ramifications. i just meant, eg in the f(x^2) case, does it matter that 1 is obtained twice? but it sounds like no.

i guess for the functions f=x^2 and g=x^4, f(Q) will be larger than g(Q), because some rationals are the square of another rational but are not a fourth power?
mieda
Profile Blog Joined February 2010
United States85 Posts
Last Edited: 2010-09-10 21:01:28
September 10 2010 21:00 GMT
#9
On September 11 2010 05:59 category wrote:
lol. I don't know about ramifications. i just meant, eg in the f(x^2) case, does it matter that 1 is obtained twice? but it sounds like no.


Right, just count it once. So for example {1,1} = {1}.

i guess for the functions f=x^2 and g=x^4, f(Q) will be larger than g(Q), because some rationals are the square of another rational but are not a fourth power?


That's right.
Assault_1
Profile Joined April 2009
Canada1950 Posts
September 10 2010 21:04 GMT
#10
Then f(x) = g(ax + b) for some rational constants a,b.


whats the domain of x, rational or real?
mieda
Profile Blog Joined February 2010
United States85 Posts
Last Edited: 2010-09-10 21:12:02
September 10 2010 21:06 GMT
#11
On September 11 2010 06:04 Assault_1 wrote:
Show nested quote +
Then f(x) = g(ax + b) for some rational constants a,b.


whats the domain of x, rational or real?


any field containing the rationals. It really doesn't matter, since the condition is only imposed on f(Q) and g(Q). You don't need to "see" bigger fields containing the rationals. Any such field is infinite anyway, so if the condition f(x) = g(ax + b) holds for evaluating x on all rationals then it's identical as polynomials (in the ring Q[x]) so evaluation of x on any field containing Q likewise.
category
Profile Joined July 2009
United States85 Posts
September 10 2010 21:09 GMT
#12
On September 11 2010 06:04 Assault_1 wrote:
Show nested quote +
Then f(x) = g(ax + b) for some rational constants a,b.


whats the domain of x, rational or real?


i would say, think of it as being the rationals.

but yeah, i am finding this quite hard, though I find the result very interesting.
sputnik.theory
Profile Blog Joined July 2009
Poland449 Posts
September 10 2010 21:16 GMT
#13
I've noticed that threads like this pop up during the school year...
ITT: TL does your math homework for you
“On the night of the murder I was at home, asleep. The characters in my dream can vouch for me.”
mieda
Profile Blog Joined February 2010
United States85 Posts
September 10 2010 21:16 GMT
#14
On September 11 2010 06:16 sputnik.theory wrote:
I've noticed that threads like this pop up during the school year...
ITT: TL does your math homework for you


Rest assured, I've already solved this. It's not a homework.
Seth_
Profile Blog Joined July 2010
Belgium184 Posts
September 10 2010 21:18 GMT
#15
May I (a non-math major) ask for an example of an f(x) and g(x) polynomial for which this is true.
Fly[DCT]
Profile Joined September 2010
Canada38 Posts
Last Edited: 2010-09-10 21:25:16
September 10 2010 21:18 GMT
#16
On September 11 2010 06:04 Assault_1 wrote:
Show nested quote +
Then f(x) = g(ax + b) for some rational constants a,b.


whats the domain of x, rational or real?


I am guessing the real or complex is fine. Once we can prove this for the real it automatically implies that it's also true for the complex.

On September 11 2010 06:18 Seth_ wrote:
May I (a non-math major) ask for an example of an f(x) and g(x) polynomial for which this is true.


Sure. f(x) = x^2. g(x) = (2x)^2.
lalalalala
Muirhead
Profile Blog Joined October 2007
United States556 Posts
September 10 2010 21:25 GMT
#17
f(Q) clearly equals g(Q) if f(x)=g(ax+b)

Thus WLOG f and g have integer coefficients that are relatively prime and 0 as their constant terms.

Suppose f(x)=a_nx^n+...a_1*x.

Suppose g(x)=b_nx^n+...+b_1*x.

Let p^r be a prime power dividing a_1 but not b_1, if such a prime power exists. Then f(x) will always be divisible by p either less than or equal to 0 times or more than r times, while g(p) is divisible by p at least once and at most r times.

So this means that f(Q)=g(Q) then a_1= plus/minus b_1

One can continue inductively through all the coefficients
starleague.mit.edu
Muirhead
Profile Blog Joined October 2007
United States556 Posts
September 10 2010 21:26 GMT
#18
Or something like that... don't have time to check everything but should be close
starleague.mit.edu
mieda
Profile Blog Joined February 2010
United States85 Posts
Last Edited: 2010-09-10 21:48:28
September 10 2010 21:29 GMT
#19
On September 11 2010 06:25 Muirhead wrote:
f(Q) clearly equals g(Q) if f(x)=g(ax+b)

Thus WLOG f and g have integer coefficients that are relatively prime and 0 as their constant terms.

Suppose f(x)=a_nx^n+...a_1*x.

Suppose g(x)=b_nx^n+...+b_1*x.

Let p^r be a prime power dividing a_1 but not b_1, if such a prime power exists. Then f(x) will always be divisible by p either less than or equal to 0 times or more than r times, while g(p) is divisible by p at least once and at most r times.

So this means that f(Q)=g(Q) then a_1= plus/minus b_1

One can continue inductively through all the coefficients


Need a lot more details, and I'm not convinced of this argument either. You're saying WLOG assume 0 as their constant terms? And then you're assuming deg f = deg g (this is true, but you didn't mention how to prove this at all). And then there's the next paragraph which doesn't seem to make much sense to me.

Enjoy your Friday anyway!
naptiem
Profile Joined July 2009
United States21 Posts
Last Edited: 2010-09-10 21:33:06
September 10 2010 21:29 GMT
#20
Here's an attempt for any field, F:

+ Show Spoiler +

Since f(F)=g(F), g(F) includes f(x) and there must be an element s of F where g(s)=f(x).

Rewrite s in the form ax+b for some a,b in F:

If x = 0, let b = s and a be any number in F.
Then ax+b = a 0 + s = s.

If x is not 0, let a = x^-1, the multiplicative inverse of x in F, and b = s - 1.
Then ax+b = (x^-1) x + (s - 1) = 1 + (s - 1) = s.

In both cases, ax+b = s and g(ax+b) = g(s) = f(x).


Edit: Never mind, I think I misread the problem.
1 2 3 Next All
Please log in or register to reply.
Live Events Refresh
Next event in 45m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
PiGStarcraft369
StarCraft: Brood War
Artosis 415
Aegong 76
yabsab 18
HiyA 3
League of Legends
Trikslyr43
Counter-Strike
Fnx 951
Stewie2K829
Super Smash Bros
PPMD97
Heroes of the Storm
Liquid`Hasu400
Other Games
shahzam893
C9.Mang0723
summit1g185
Maynarde125
Mew2King83
Sick78
Organizations
Other Games
gamesdonequick618
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 17 non-featured ]
StarCraft 2
• Berry_CruncH163
• davetesta61
• intothetv
• IndyKCrew
• sooper7s
• AfreecaTV YouTube
• Migwel
• LaughNgamezSOOP
• Kozan
StarCraft: Brood War
• Azhi_Dahaki4
• STPLYoutube
• ZZZeroYoutube
• BSLYoutube
Dota 2
• masondota21633
Other Games
• imaqtpie1277
• Scarra832
• Shiphtur342
Upcoming Events
Replay Cast
45m
RSL Revival
10h 45m
Cure vs Percival
ByuN vs Spirit
WardiTV Qualifier
16h 45m
PiGosaur Monday
1d
RSL Revival
1d 10h
herO vs sOs
Zoun vs Clem
Replay Cast
2 days
The PondCast
2 days
RSL Revival
2 days
Harstem vs SHIN
Solar vs Cham
Replay Cast
3 days
RSL Revival
3 days
Reynor vs Scarlett
ShoWTimE vs Classic
[ Show More ]
uThermal 2v2 Circuit
3 days
SC Evo League
4 days
Circuito Brasileiro de…
4 days
Sparkling Tuna Cup
5 days
Liquipedia Results

Completed

Acropolis #3 - GSC
2025 GSL S2
Heroes 10 EU

Ongoing

JPL Season 2
BSL 2v2 Season 3
BSL Season 20
Acropolis #3
KCM Race Survival 2025 Season 2
NPSL S3
Rose Open S1
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Murky Cup #2
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25
BLAST Rivals Spring 2025
MESA Nomadic Masters
CCT Season 2 Global Finals
IEM Melbourne 2025
YaLLa Compass Qatar 2025
PGL Bucharest 2025

Upcoming

CSLPRO Last Chance 2025
CSLPRO Chat StarLAN 3
K-Championship
SEL Season 2 Championship
Esports World Cup 2025
HSC XXVII
Championship of Russia 2025
RSL Revival: Season 1
BLAST Open Fall 2025
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
FISSURE Playground #1
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2025 TLnet. All Rights Reserved.