cevi

Why would SHA-256 be vulnerable to quantum computing? Grover's algorithm only gives a square-root speedup for reversing hash functions, and that's in the best-case scenario where there are no engineering issues (e.g. the need for error correction) which could create polynomial overhead. That still leaves you with 128 bits of security.

Quantum computing could certainly break elliptic curve cryptography, but my understanding is that this only becomes an issue if you publish your public keys (e.g. if you use your key to digitally sign a message) instead of just publishing their hash, which is not standard practice in Bitcoin (for exactly this reason).

Perfect accuracy is an insane goal. Much better is to develop the skill of finding and correcting your mistakes. Part of this is doing frequent "sanity checks" - for instance, if you are computing an area, and you get the answer -3, probably you made an algebra mistake somewhere earlier, and you should find and fix it before going on (some ways of checking your work also help you pinpoint where the mistake occurred, others are less helpful for that). Another way to check your work is to try plugging in numerical values for all of the variables and going through the arithmetic to check all of the steps (if you need to check your arithmetic, try something like "casting out 9s").

Learning to find and correct your mistakes will at first make it take ten times as long to solve any problem as just scribbling your way to an answer. But if you practice it, you will discover two things:

- with practice, the overhead of finding and correcting mistakes drops significantly,

- the feedback you get from noticing your mistakes helps you avoid making those mistakes in the future. Eventually mistakes become extremely rare, and you can go through a very long computation without making a mistake, even if you don't bother checking for them any more!

The author claims to have a proof that NP = coNP = PSPACE along the following lines: first they describe their favorite axiomatic logical system, then they claim to have a method to compress quasipolynomial-sized proofs in this system to polynomial-sized proofs. If their claimed proof worked, it would be a breakthrough the likes of which math has never seen before - NP = coNP means that every easily stated puzzle with no solution has a short proof of unsolvability (NP = coNP is widely believed to be false).

Looking at some of the previous papers (such as [1]) building towards the proof (which appear to have actually been published?!), I don't see any magic. It looks complex enough that the author probably fooled themself, but there doesn't seem to be any amazing new algorithmic ingredient such as the idea behind the fast fourier transform or fast matrix multiplication. Color me extremely skeptical.

[1] https://arxiv.org/pdf/1907.03858.pdf

I have ten or so tantalizing questions which I don't know how to solve stuck in the back of my head at all times. Some of these are truly hopeless (i.e. P vs NP), others seem like something I can probably figure out but just haven't found the right perspective yet (these tend to be more obscure). This list of questions changes over time - sometimes problems actually get solved, sometimes I lose interest in them, sometimes I learn about a completely new area and add a bunch of new problems to my list of things to think about.

If I'm at a social gathering and the people are boring, I take out a piece of paper and start trying to visualize some aspect of a problem I've been stuck on for a while, or compute what happens in some particular special situation. In order to carry out the computations, I find myself making up paper-and-pencil algorithms, typically variations of dynamic programming with some specialized bookkeeping notation so that I can see at a glance what is going on on the paper. My scribbles probably only make sense to me - lots of bipartite graphs with labeled vertices, or directed graphs with decorations on their edges, or sequences of column vectors full of letters instead of numbers with groups of little dots underneath them, or attempts to draw small three-uniform hypergraphs...

Every so often I manage to rephrase one of the problems which is stuck in the back of my head in a new way. Then I think, hey, wait - maybe someone has studied this type of problem (i.e. the rephrased problem) before! I search around, and find some research area that is almost but not completely unlike what I was hoping for, and try to read some introductory material about it. Maybe I download a textbook on, say, "unification", and just read the chapter on "confluent rewriting systems", since I think those might help with the algebra problem I'm interested in. It doesn't, but it gives me a new pencil-and-paper algorithm to play with, so I fill up a blank piece of paper trying it out.

I also have an infinite backlog of books on math that is just plain interesting to me, but which I don't expect to find any use for. Things like advanced set theory, which is interesting from a philosophical point of view (how do we come to be convinced of new axioms? Is it possible to become convinced that "measurable cardinals" really exist?), or average case complexity (is providing a theoretical foundation to cryptography hopeless?), or statistical mechanics (what are all those physicists talking about when they bring up the "Ising model"?). I go through these at a much slower pace, sometimes only getting through the introduction before I have to put them to the side to focus on other things, but occasionally I get a solid two weeks of uninterrupted time to focus on one of these and blow through... well, the first two-thirds of a book, putting off the last third to some time when I actually need to know it.

About once a year, I'm in a situation (often a conference, sometimes an unusually interesting party) where there is someone else I can talk to about my interests.

Direct link to the article: https://www.nature.com/articles/s41586-021-04203-w

Finance is one field which is desperate for good coders, and which is using tons of outdated software. I'm sure there are other fields like that, too - think really old companies with critical software that can't be ported to newer paradigms in case some tiny oversight breaks it.

The arxiv version isn't very different from the published version, if you end up facing a paywall: https://arxiv.org/pdf/1801.09488.pdf

This is not a proof, just statistical evidence for the Riemann Hypothesis. If you are looking for statistical evidence for RH, the evidence collected by mathematicians already is significantly stronger than what they have...

The Game of Life on an infinite grid, starting from a uniformly random pattern (i.e. each cell is either alive or dead with probability 1/2), gives you a whole multiverse which is governed by rules different from our own which probably contains intelligent life somewhere within it. Is that what you are looking for, or are you instead asking for an alternate universe where the rules of mathematics itself (or possibly even logic) are different?

There are mathematical models of alternate universes where math and logic don't work, in the sense that a person living in those universes would easily prove that 1 = 0 from the Peano axioms (and would presumably give up on either the Peano axioms or first-order logic as a result). These mathematical models are uncomputable (so we can't actually simulate one like we can with the Game of Life), but they can be defined unambiguously and could even be simulated if we had access to a halting oracle. But even these alternate universes where math doesn't work are still built out of math - it's hard to even imagine a model of something which isn't built out of math.

It's important to acknowledge just how much randomness goes into the process every year - some years the US team is very strong, other years some of the competitors have a bad day. Students graduate, or decide to pursue a different summer activity, and there often isn't anyone on the same level to replace them. Saying that the US "slipped" to third is just nonsense.

The fact that China's performance in the IMO is so consistent year after year is a bit mind-boggling, to be honest. I suspect that part of their dominance is a heavy focus on algebra, which is all about consistently getting the job done. Top US students are more likely to have studied "fun" math, like combinatorics, geometry, or number theory - and even if you are a superstar at combinatorics, you can still miss an easy combinatorics problem if you happen not to see the right way to look at it.

Why not?

I'm always happy to see a sober viewpoint on category theory - too many enthusiasts treat it as panacea. That said, I have actually used category-theoretic language to state interesting facts about relations! It turns out that relations can be embedded into concrete categories in a fairly natural way:

To describe a ternary relation on three objects/sets/spaces/etc. A,B,C of some category, you pick an object R and three maps pi_A : R -> A, pi_B : R -> B, pi_C : R -> C. In a concrete category, we can then say that elements/points/etc. a in A, b in B, c in C are related by R, if there is some element r in R such that pi_A(r) = a, pi_B(r) = b, and pi_C(r) = c.

The above approach gives a reasonable way to define the relations which are "compatible with" a given category. If you apply it in the category of sets, you basically get the ordinary sort of relations (with a bit of extra fluff if the map R -> A×B×C is not injective), but if you apply it in categories with more algebraic structure, then you get relations which respect that extra structure.

(Of course, as usual, category theory is only being used here to state things more clearly - I didn't find this perspective to be particularly helpful for actually proving the things I was interested in proving.)

Sadly, this page hasn't been updated since 2016. I'd love to see some of the more recent attempts at proofs collected somewhere!

Unfortunately, randomly permuting the input takes O(nlog(n)) steps (you need at least this much time just to read in sufficiently many random bits). Perhaps a clever parallel architecture could reduce the runtime?

No - I checked.

The author says that mathematicians find math outside their own field to be boring and difficult to understand. As a mathematician, I think he's rather missing the point:

- mathematics is boring to everyone right up until the moment you need it. Then suddenly it becomes very interesting.

The way mathematicians typically read papers is not by randomly picking through recent submissions to the arxiv and dutifully reading everything they come across. Instead, they stumble on a hard problem in their own research which they don't know how to solve, and they search to see if anyone else has worked on it before. The paper you would have discarded as pointlessly abstract or ridiculously overspecialized just yesterday suddenly reads like a riveting novel today. No amount of creative writing tips would have made it any more interesting to you yesterday - unless the writers happened to anticipate the exact reason you would end up becoming interested in it ahead of time.

Oh, I didn't know about this! "Get past chapter four of any textbook on quantum field theory" has been on my to-do list for quite a while.

There is no solid math or physics which supports time travel. There are a lot of cases where people claim to have found some loophole or another in the impossibility proofs for time travel, sketching out a model that looks plausible at first glance, but they all end up postulating some blatantly non-physical entity somewhere along the way (i.e. cosmic strings, negative energy density, ... - I've gotten my hopes up quite a few times).

Speculating about parallel universes is a different story - even if they exist, we can't travel to them, so there is no sense in claiming that we can somehow harness their power. It's a philosophical question, not a physical one. In contrast, the rules of quantum mechanics (when phrased in terms of density matrices, at least) only describe things we can actually measure and observe, and people actually do test every single aspect of the predictions quantum mechanics makes.

Unlike perpetual motion or free energy, the math and physics behind quantum computing is rock solid - the possibility is baked into the framework of quantum mechanics at an absolutely fundamental level. Even if it turned out that all of quantum field theory was completely bogus, I would still expect the basic framework of quantum mechanics (i.e. unitary evolution, the Born rule for converting amplitudes to probabilities, density matrices describing mixed states) to be correct.

If quantum computing was not possible, that would mean that everything we thought we knew about physics was hopelessly wrong. Physics would have to be much stranger - we'd have to give up on either locality (i.e. causation being limited by the speed of light), reversibility (closely related to conservation of energy), or nondeterminism in order to make the math work out. There are several papers in the literature that derive quantum mechanics from these or related assumptions (often together with some extra technical detail, that differs between approaches):

https://arxiv.org/abs/quant-ph/0101012 https://arxiv.org/abs/1011.6451 https://arxiv.org/abs/0911.0695

This is the topic of "clone theory": the study of which (multivariable) operations can be created by composing together a starting collection of operations. Post's lattice is a complete description of which gates can be generated from which other gates in two-valued logic, but the subject becomes much more difficult in multivalued logic.

If you are just interested in whether a given gate would allow you to generate all possible operations in a multivalued logic, then there is a nice result called the Rosenberg Completeness Theorem that says, roughly speaking, that any operation which doesn't have a nice property (from a certain explicit list of nice properties, such as monotonicity, linearity, etc.) will generate all other operations. To answer your question, NAND is special because it isn't monotone, isn't linear (in the sense of not being a linear function modulo 2), isn't self-dual, doesn't send all-0s to 0, and doesn't send all-1s to 1.

Somehow this article avoided mentioning Smart Pipe ("Smartpipe, Inc., is a registered sex offender") the whole way through.

I really like the ideas behind Bitcoin. However, the system requires every single on-chain transaction to be stored and mirrored on every single full node in existence. As more people adopt Bitcoin, and as time continues to advance, this makes the storage requirements grow to insane amounts. Whether hard drive storage space will be able to keep increasing quickly enough to keep pace is unclear to me.

Quantifiers are what is missing in probability theory but present in logic - while we could potentially write down mixtures of quantifiers and probabilistic symbols, we don't have great ways to interpret them or to reason about them. That is the point he is trying to make.

I know someone who wanted to build up a solid mathematical foundation after years of considering themself to be bad at it, and ended up loving Spivak's book on calculus. (Another well-written book on calculus, in a very different style, is the classic book "Calculus Made Easy" - this book is old enough to be available on Project Gutenberg.)

You can learn linear algebra without learning calculus, but to really care about linear algebra you have to know why it's useful. The main lesson from (multivariable) calculus is that you should approximate functions by linear functions whenever possible - so the basis of almost everything else in math is a deep understanding of linear functions (and the occasional quadratic when you need that little bit of extra oomph). Once you manage to convince yourself to care about linear functions, the subject magically becomes easier to learn. I don't have any especially great textbook recommendations - perhaps Strang's book?

The nice thing about math is that once you reach a certain level, self-assessment becomes extremely reliable. From that point on you can learn math on your own without worry!

The key is to always have some concrete procedure available to check the results of what you studied. If you are solving a system of equations, the concrete procedure is to check if your answer actually solves those equations. If you are taking a derivative, the concrete procedure is to numerically compute the expression (f(x+h) - f(x))/h for a really small value of h, and check if it is approximately the same as your computed value of f'(x). If you are integrating a function, the concrete procedure is to take the derivative of your answer and see if you got the original function back, or to numerically compute a Riemann sum.

If you are writing a proof... that is harder to verify on your own, but there are still ways to do it. You could think of a particular example and follow the steps of the proof in that particular situation and see if they work as advertised. You could try to rephrase the proof as a method for doing computations, and check that the method of doing computations gives correct results. You could attempt to transcribe the proof into a formal language, or even all the way to an interactive theorem prover. (Of course, someone who can successfully use an interactive theorem prover probably doesn't need advice on verifying proofs - they aren't very usable pieces of software yet.)

When learning a new area of math, your first question should be: how do I concretely check whether basic claims people are making are true or not? For this you need to know a few examples that illustrate different behaviors that can occur, and you need to understand these examples like the back of your hand. You also need at least one reliable method of concretely computing with whatever objects are being studied. The moment you don't feel like the subject is grounded in something concrete anymore, stop, try to find some examples, look for another book, maybe just put the topic to the side and study something else.

While computer scientists might expect slightly faster factoring algorithms to exist than the ones we know of - perhaps exp((# bits)^0.25) is plausible - I think the majority of computer scientists, including Aaronson, would be completely shocked if it was possible to factor integers in polynomial time.

Factoring isn't a problem like testing primality, or graph isomorphism, where we had algorithms that worked well in practice but not perfectly theoretically for many years before the major breakthroughs. While it wouldn't be quite as mind-boggling to find a fast factoring algorithm as it would be to efficiently solve SAT - factoring almost certainly isn't NP-complete - it definitely seems to fit somewhere into the "hard" side of things from the standpoint of classical complexity.

One way to think of it is this: when problems can be solved efficiently, there is generally some sort of nice algebraic structure that makes them easy. Nice, exploitable algebraic structure is extremely rare: if you haven't found hints of it after putting in a fair amount of effort, it probably isn't there at all. Of course, we can't currently rule out the possibility that there are secret ghostly algebraic structures that will render everything easy lurking just beyond our current knowledge, but intuition from studying our best known algorithms and our complete lack of progress on truly hard problems indicates that this isn't the case.

This assumption is correct - the quanta article left out quite a bit of detail about how forcing actually works, while trying to give some hint of the philosophy behind it.

As it turns out, you can still apply the forcing technique even if you start with the whole set of all real numbers. What happens in this case is a bit surprising: since there's no legitimate way to add new real numbers that weren't there previously, the forcing procedure cheats by pretending that real numbers have nonstandardly long decimal expansions.

To make the way it cheats a bit more concrete, we start by first imagining that there are "nonstandard integers" n which are bigger than all of the "true" integers from our starting model. Once we assume that these integers exist, we have to commit ourselves to providing answers to questions like, "what is the nth digit of pi?", "what is the n+1th digit of pi?", and so on in a consistent way. By answering these questions, we embed all of the original real numbers from our starting universe into the new universe. But the point is that now that we have all of these extra digits to play with, all of the original real numbers only fill up a tiny subset of the potential "real" numbers in the new universe, and we can happily go back to forcing new ones in.

Of course, adding nonstandard integers to our universe is quite a violent change, so we also have to worry about whether we've accidentally screwed up the way that the ordinals work in the process (for instance, the "first infinite ordinal" in the new universe now contains all of the nonstandard integers we added), and we need to worry about this again when we get around to forcing the new reals in. So a whole lot of technical details need to be ironed out carefully, using a few clever combinatorial arguments, to make the whole charade come together.

All of this cheating happens under the hood in a way that is not obvious at all when you first go through the technical details of the forcing construction. I only learned about the full perspective from Joel David Hamkins's "naturalistic account of forcing".

Mathematicians do consider "just pick an arbitrary element" sufficient. This is baked into the system of "first order logic" - the standard use of existential quantifiers in logic allows for proofs that make any finite number of arbitrary choices, but the proof gets longer as the number of arbitrary choices increases (so a straightforward attempt to prove that you could make an infinite sequence of arbitrary choices, in first order logic, would lead to an infinitely long proof). The first order logical system behind modern mathematics is both powerful, and limited, in this very particular strange way.

You could definitely come up with alternative logical systems to first order logic where "just pick an arbitrary element" is not considered a valid proof strategy, but this would be more an exercise in philosophy and logic than in mathematics. There are good practical reasons for mathematicians to like classical first order logic (such as the fact that Godel's completeness theorem applies to it), so it would be hard to convince most mathematicians to switch to any other logical system. Making classical first order logic weaker makes it unpleasant for the purposes of getting things done for not enough benefit (although intuitionists will fight you over this claim), while trying to make it stronger leads to problems where your logical system needs to magically give you access to truths which are uncomputable in order to be complete ("abstract model theory" tries to make this claim precise).

The trouble is that first order logic doesn't have a built-in concept of "infinity", let alone a rule that says it is valid to "just pick an arbitrary infinite sequence", let alone the full strength of the axiom of choice (which applies even to sets so large that their elements can't be listed via a "sequence"). Such a logical rule can only be added in a logical system which can talk about arbitrary sets or infinite sequences in the first place, which goes beyond first-order logic. So rather than having this rule be a rule of pure logic, the workaround is to add it as a mathematical axiom that applies to the (first order) mathematical theory of sets, which is meant to be a practical approximation to the (ungraspable) "true" collection of rules for "higher order logic".

As far as I can tell, there is no such insight here - in the middle of page 13 they admit that in their solution, the weak energy condition is violated, and even that:

"No amount of modification to the configuration could get rid of these WEC-violating regions."

If I'm reading this correctly, all they have done is found a solution that has positive Eulerian energy density according to one particular reference frame, but not according to other reference frames. (I'm not a physicist, so please correct me if I'm wrong.)

This should be obvious, but just in case: do not store your bitcoin at this address.