# What is a "non-constructive proof?"

Dutle, Aaron M. (LARC-D320) aaron.m.dutle at nasa.gov
Tue Feb 18 12:34:11 EST 2020

"There are at least three kinds of ?non-constructive proofs? that I have seen:
(1) A theorem that certain equations have finitely many solutions, with no bound given that would allow one to exhaustively search for them
(2) A theorem that a certain equation has a solution, with no bound given, but a guarantee that searching will eventually find one
(3) A counting argument that an object with certain properties of a certain size must exist, which comes with an implicit exponential bound on the search but no efficient construction.
"

Classics of type (3) abound in combinatorics. Particularly in proofs where the best bounds are found using probabilistic methods. A (fairly) simple classic is "high girth and high chromatic number." This says that for all m,n, there is a graph G with girth(G)>m and \chi(G)>n. This is somewhat counterintuitive, because high chromatic number is generally form having a large clique, while girth is the length of the shortest cycle. The result is shown by choosing an appropriate random graph, and showing that as n->\infty, the probability of choosing a graph with both properties simultaneously is positive. Math majors with some background in probability and a little graph theory should be able to follow a well-presented proof. The classic reference for this type of problem is "The Probabilistic Method" by Noga Alon and Joel Spencer.

Aaron M. Dutle
Research Computer Scientist
Safety-Critical Avionics Systems Branch
NASA Langley Research Center
757-864-9326

﻿On 2/18/20, 12:13 PM, "fom-bounces at cs.nyu.edu on behalf of fom-request at cs.nyu.edu" <fom-bounces at cs.nyu.edu on behalf of fom-request at cs.nyu.edu> wrote:

Send FOM mailing list submissions to
fom at cs.nyu.edu

To subscribe or unsubscribe via the World Wide Web, visit
or, via email, send a message with subject or body 'help' to
fom-request at cs.nyu.edu

You can reach the person managing the list at
fom-owner at cs.nyu.edu

When replying, please edit your Subject line so it is more specific
than "Re: Contents of FOM digest..."

Today's Topics:

1. What is a ?non-constructive proof?? (Joe Shipman)

----------------------------------------------------------------------

Message: 1
Date: Sun, 16 Feb 2020 21:46:01 -0500
From: Joe Shipman <joeshipman at aol.com>
To: Foundations of Mathematics <fom at cs.nyu.edu>
Subject: What is a ?non-constructive proof??
Message-ID: <CEB385D3-FBA7-4017-BBCF-5F115B5B0234 at aol.com>
Content-Type: text/plain; charset=utf-8

There are at least three kinds of ?non-constructive proofs? that I have seen:
(1) A theorem that certain equations have finitely many solutions, with no bound given that would allow one to exhaustively search for them
(2) A theorem that a certain equation has a solution, with no bound given, but a guarantee that searching will eventually find one
(3) A counting argument that an object with certain properties of a certain size must exist, which comes with an implicit exponential bound on the search but no efficient construction.

Can people provide examples of each of these three types where the proof can be presented to undergraduate math majors, and where no improvement is known? (In other words, a nonconstructive proof of each type where no proof is known of an easier type.)

? JS

Sent from my iPhone

------------------------------

_______________________________________________
FOM mailing list
FOM at cs.nyu.edu