• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 20:00
CEST 02:00
KST 09:00
  • 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 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, Maru3BGE Stara Zagora 2025: Info & Preview27
Community News
Classic & 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.4Code S RO8 Results + RO4 Bracket (2025 Season 2)12BGE Stara Zagora 2025 - Replay Pack2Weekly Cups (June 2-8): herO doubles down1
StarCraft 2
General
Rogue & 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. Classic & herO RO8 Interviews: "I think it’s time to teach [Rogue] a lesson." Code S RO8 Results + RO4 Bracket (2025 Season 2) Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho I have an extra ticket to the GSL Ro4/finals
Tourneys
[GSL 2025] Code S: Season 2 - Semi Finals & Finals $3,500 WardiTV European League 2025 Sea Duckling Open (Global, Bronze-Diamond) SOOPer7s Showmatches 2025 RSL: Revival, a new crowdfunded tournament series
Strategy
[G] Darkgrid Layout Simple Questions Simple Answers [G] PvT Cheese: 13 Gate Proxy Robo
Custom Maps
[UMS] Zillion Zerglings
External Content
Mutation # 477 Slow and Steady Mutation # 476 Charnel House Mutation # 475 Hard Target Mutation # 474 Futile Resistance
Brood War
General
TRUSTWORTHY BITCOIN RECOVERY EXPERT HIRE SLAYER CO ASL20 Preliminary Maps BGH Auto Balance -> http://bghmmr.eu/ Recent recommended BW games BW General Discussion
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
Path of Exile Nintendo Switch Thread Stormgate/Frost Giant Megathread 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 UK Politics Mega-thread Russo-Ukrainian War Thread Vape Nation Thread
Fan Clubs
Maru Fan Club Serral Fan Club
Media & Entertainment
Korean Music Discussion [Manga] One Piece
Sports
Formula 1 Discussion 2024 - 2025 Football Thread 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: 31833 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
Cheesadelphia
15:00
Cheeseadelphia 2025
Gerald vs EpicLIVE!
TBD vs FuturE
CranKy Ducklings444
davetesta111
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
RuFF_SC2 81
StarCraft: Brood War
Britney 15663
NaDa 32
Dota 2
LuMiX1
League of Legends
Grubby2827
Dendi1625
Counter-Strike
Fnx 1343
Stewie2K988
Foxcn599
Super Smash Bros
Mew2King57
Other Games
tarik_tv11913
summit1g9701
C9.Mang0888
ViBE157
Trikslyr78
Organizations
Other Games
gamesdonequick1149
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 20 non-featured ]
StarCraft 2
• Hupsaiya 81
• RyuSc2 75
• musti20045 28
• HeavenSC 23
• tFFMrPink 10
• IndyKCrew
• AfreecaTV YouTube
• intothetv
• Kozan
• sooper7s
• LaughNgamezSOOP
• Migwel
StarCraft: Brood War
• RayReign 11
• STPLYoutube
• ZZZeroYoutube
• BSLYoutube
Dota 2
• Ler91
League of Legends
• Doublelift5564
Other Games
• imaqtpie1843
• Shiphtur262
Upcoming Events
GSL Code S
8h 1m
Rogue vs herO
Classic vs GuMiho
Sparkling Tuna Cup
10h 1m
WardiTV Qualifier
16h 1m
BSL: ProLeague
18h 1m
Bonyth vs Dewalt
Cross vs Doodle
MadiNho vs Dragon
Replay Cast
1d
Wardi Open
1d 11h
Replay Cast
2 days
Replay Cast
2 days
RSL Revival
2 days
Cure vs Percival
ByuN vs Spirit
RSL Revival
3 days
herO vs sOs
Zoun vs Clem
[ Show More ]
Replay Cast
4 days
The PondCast
4 days
RSL Revival
4 days
Serral vs SHIN
Solar vs Cham
Replay Cast
5 days
RSL Revival
5 days
Reynor vs Scarlett
ShoWTimE vs Classic
uThermal 2v2 Circuit
5 days
SC Evo League
6 days
Circuito Brasileiro de…
6 days
Liquipedia Results

Completed

Proleague 2025-06-11
BGE Stara Zagora 2025
Heroes 10 EU

Ongoing

JPL Season 2
BSL 2v2 Season 3
BSL Season 20
KCM Race Survival 2025 Season 2
NPSL S3
Rose Open S1
CSL 17: 2025 SUMMER
2025 GSL S2
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

Copa Latinoamericana 4
CSLPRO Last Chance 2025
CSLPRO Chat StarLAN 3
K-Championship
SEL Season 2 Championship
Esports World Cup 2025
HSC XXVII
Championship of Russia 2025
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.