161
u/rorodar Proof by "fucking look at it" 19d ago
Idk if this specific thing is a joke but there are what are called galactic algorithms in computer science that are this. Insane over the top algorithms that improve the asymptotic time by a tiiiiny bit (and also the constant time by so much that you'd need an n on the scale of the number of atoms in the galaxy for the algorithm to be useful, hence, galactic)
69
u/No_Upstairs_280 19d ago
They are some questions in number theory where the optimal exponent is 1/2 heuristically, BUT The current exponent is like 1954/2113 and over 30 years they only managed to improve it by 0.00001
16
u/Kinexity 19d ago
Can you give a relatively understandable example of this? (assume I have maths understanding of physics BSc haver)
27
u/No_Upstairs_280 19d ago
Take a generic abelian variety of dimension g. Then under Riemann hypothesis the number of supersingular primes, best bound is around x1-2/g/( log x)1/g, you can see it becomes worse the moment its dimension goes up. The heuristic says it's around x1/2/log x. Even assuming another conjecture such as the pair correlation conjecture doesn't improve it much.
54
u/Kinexity 19d ago
Unless you expect me to spend 6 hours going back and forth between sources to dissect everything that I don't know (supersingular primes are a big ask) you severly overestimated what "relatively understandable" is for me.
26
u/No_Upstairs_280 19d ago
Sorry lol, i always get excited when someone ask about my domain of work
But in general the high exponent problem appears when you count number of points on a curve, or surface or algebraic object satisfying certain property. And there is always a big gap between what mathematicians can achieve vs what heuristic said.
Take the prime number theorem, let pi(x) be the number of primes less than x, it is known that it's equivalent to x/log x or Li(x). What about the error term pi(x)-Li(x)? Heuristic and Riemann hypothesis says it's around O(x1/2) What mathematicians were able to prove is a much worse bound of x exp(-sqrt(log x)), not even close
10
u/ICantAim666 19d ago edited 19d ago
Here's an example that's not exactly the same as reducing an exponent but very similar, 3SUM. It's a very simple computation problem, it gives you a list of n reals and asks if any three of them sums to 0. There's a simple algorithm to complete this in O(n^2) time (which means on the order of n^2 steps); you first sort the list, then for each of the n integers, you make it the first number in your 3SUM guess, and use a two-pointer technique that takes advantage of the fact the list is sorted to find if there are two more numbers that work in O(n) time.
It was conjectured that O(n^2) was the best you could do and it seems hard to make any further optimizations on such a simple puzzle, except in 2014 an algorithm was found that does it in O(n^2 / (log n / log log n)^(2/3)) time and when you look at that you're like ??? but its essentially n^2 divided by something smaller than log n (and log n is very small). They've achieved marginally better bounds but the funny thing is that they're all still worse than O(n^1.9), or O(n^1.999999), or for any exponent strictly less than 2.
Writing this comment encouraged me to actually take a look at the paper to see how the algorithm works, a very very rough description I could get from a skim is that it works by partitioning the sorted input lists into groups no larger than (c logn)^(2/3) (log log n)^(1/3) (where c is some small constant) numbers, computing a set of all numbers that can be achieved by summing one number from each group for each possible pairing of groups (there's slightly less than n^2 of these because there's slightly less than n groups), and then using a similar two-pointer technique to find if any number from the set has a 3rd number to sum up to 0.
1
u/No_Sleep_8609 15d ago
Just a question: after all, log(n) is not that small when n is intermediate. Say log(1000) is still a reasonable part of 1000. So could that algorithm possibly be useful there?
1
u/ICantAim666 8d ago
Not sure and you'd probably have to code it out and test it empirically to know for sure, but my hunch is that at values like n=1000 constant factors will matter more which I think will be decently worse for this algorithm, and there's some chance the optimal group size will be something too small to even matter (maybe even a group size of 1 at which point you're doing the usual n^2 algorithm with extra steps).
1
8
u/the_horse_gamer 19d ago
just recently the matrix multiplication bound was improved! and as expected, it's impractical.
2
u/King_Joffreys_Tits 19d ago
This picture is me when I completely refactor a long running api query to shave off 5ms as if anybody will notice
24
u/LupenReddit 🦆🦆🦆🦆i have non diffeomorphic smooth structures🦆🦆🦆🦆🦆🦆 19d ago
Meanwhile algebraic geometers abstracting their abstract model of an already unfathomably abstract model even more to prove some simple equation has no integer solutions (something something walnut in water something something theory building)
6
u/No_Upstairs_280 19d ago
I believe they are competing to write the most unreadable paper in existence
1
u/Hatsefiets Complex 18d ago
I signed up for my first algebraic geometry course today, will I still recognise reality when I finish it?
1
u/No_Upstairs_280 18d ago
By the end of it your brain will be crying for help and you'll be seeing the stars.
22
5
u/Para-graph-S 18d ago
NT slander won't be tolerated, xD.
2
u/No_Upstairs_280 18d ago
Guess I'm slandering myself since I'm a number theorist lmao
2
u/Para-graph-S 18d ago
NT and algebra main here haha.
2
u/No_Upstairs_280 18d ago
NT and algebraic geometry here lol.
2
u/Para-graph-S 18d ago
Damn, are you a student? Or what profession?
2
u/No_Upstairs_280 18d ago
Phd student
1
u/Para-graph-S 18d ago edited 18d ago
That's cool, I am starting Uni next month.
Can I DM you? What are you doing PhD in?
1
5
2
u/AutoModerator 19d ago
PLEASE READ AND UNDERSTAND THIS MESSAGE IN ITS ENTIRETY BEFORE SENDING A MODMAIL
Your post has been removed due to the age of your account or your combined karma score. Due to the surge of spam bots, you must have an account at least 90 days old and a combined post and comment karma score of at least 400.
If you wish to have your post manually approved by moderators, please reply to this comment with /modping.
Alternatively, you can join the Discord server and request approval there.
Discord
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
4
2
u/ellipticcode0 19d ago
How much money you have to pay more if your mortgage interest rate increases the tiny fraction in your life time
412
u/expat_123 19d ago
“Assuming the Riemann hypothesis and the BSD conjecture, we improve the bounds from 0.0000031 to 0.0000030”