On Alien Truths

I had been discussing some problem with a friend a few months back, and we stumbled upon a way to solve that problem that involves a lot of computation, and we had a conversation about how some statements cannot really have elegant proofs.

I discovered that that month's issue of ACM Communications talked about this idea, which they called Alien Truths. And furthermore, I found some evidence from formal logic embracing this idea: namely Godel's Speedup Theorem, which says (to quote wikipedia):

there are theorems whose proofs can be drastically shortened by working in more powerful axiomatic systems.

I attach a couple of emails below

Hi;

We had a conversation last Monday about how I believe that not all problems have elegant solutions, as a comment on the problem of inverting Hilbert Matrices. I recently found some interesting material related to that view.

In the August Issue of Communications of the ACM, a concept called Alien Truth has been discussed (see pg 8 of the pdf version, here). They define it as something like this:

> [...] a truth statement is alien if humanly understandable case-splits are way too big for any plain brute-force method, but there exists a giant case-split that mysteriously avoids an enormous exponential effort.

And I found a relevant Wikipedia Article too: Godel's Speedup Theorem

--Agnishom

This was the Boolean Pythagorean triples problem:

> [...] if it is possible to color each of the positive integers either red or blue, so that no Pythagorean triple of integers a, b, c, [...] are all of the same color.

And you could find the link to the pdf of the article in this attached email.

--Agnishom

P.S: Look at page 22 of this document for some practical uses of SAT solvers. (Because apparently Boolean Pythagorean Triples was not practical enough.)

What are some problems you know you wish had more elegant proofs?

#Logic

Note by Agnishom Chattopadhyay
3 years, 1 month ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

The four color theorem, perhaps?

Nick Turtle - 3 years, 1 month ago

Log in to reply

Yes, that came to my mind too

Agnishom Chattopadhyay - 3 years, 1 month ago
×

Problem Loading...

Note Loading...

Set Loading...