Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why Discrete Math Is Important

artofproblemsolving.com

Post reply on HN
Print view View original

101–110 of 127 posts

Re: Why Discrete Math Is Important

#101

Post by ChrisLomont »

Chris2048 wrote: post #67
ChrisLomont wrote: post #56

Earlier quoted context omitted.

>because the universe is discrete Many aspects of the universe are not known to be discrete, such as space, time, energy, and much, much more. It's not unreasonable that there are discrete and continuous aspects to the universe. Many things that pop science treats as discrete, such as an electron, are most accurately described as interactions of a continuous fields via topological quantum field theories. Treating the…

"not known to be discrete" does not imply "It's not unreasonable that there are discrete and continuous aspects to the universe"; it is not known that anything is continuous either.

The theories that best model every known experiment are continuous. General relativity models large scale phenomena to incredible precision, and is continuous. Predictions made by it around 100 years ago are still being tested and found true, such as gravitational waves.

The Standard Model, which models everything else, is continuous. A specific part of it, QED, is the most accurate theory known, agreeing with experiment to better than 10 parts in a billion.

There is no known violation of these two theories, which explain all of the observable universe. There is an issue on how to glue them together, and one of the leading methods, string theory, is also continuous. I am unaware of any theory that can replace these that has no continuous parts, such as symmetries.

> it is not known that anything is continuous either

Every physics theory that we use to explain the universe is continuous, and not a single one is not, so I'm betting that there are continuous things in reality.

Re: Why Discrete Math Is Important

#102

Post by BeetleB »

jeremysalwen wrote: post #99
BeetleB wrote: post #72

Earlier quoted context omitted.

>Hence interesting is solving discrete problems with "continuous" tools - like e.g. http://ac.cs.princeton.edu/home/ I'm often interested in the opposite: Solving continuous problems by going to the discrete domain. I'm not a mathematician, but I did enjoy taking math courses and dabbling a little. My personal highlight was when I was struggling for months to solve a continuous variable problem, but then one day I de…

So is this the solution? The probability that all numbers are less than x is equal to x^n. So then you take the derivative of that to get the probability that the maximum us is exactly x. n x^n-1. Then calculate the expected value as integral from 0 to 1 of x n x^n-1 = n/n+1.

Too lazy to think deeply about it, but it sounds right. You start with the cumulative distribution function and get the pdf from it, which looks like what you're doing.

Really simple solution. Problem is simple enough that this could be a standard HW problem in a probability course. Yet so many people (including myself) did not see it. We kept doing multiple integrals (n integrals for n points) and tried using induction on it.

This was actually a subproblem of the real problem. The real problem was: Given n points chosen randomly on a circle, construct the n-sided polygon. What is the probability that the center of the circle is inside the polygon? Since I worked on it, the problem has shown up on the Internet in various places (usually for the special case of n=3 - triangles, but I think I've seen the general one posted here and there). I don't recall if anyone came up with the same solution I did for the general case - I think one site had it.

Re: Why Discrete Math Is Important

#103

Post by VyseofArcadia »

CogitoCogito wrote: post #53
enriquto wrote: post #29

Discrete math is important because the universe is discrete. Continuous math is an approximation that sometimes, but not always, is rather convenient. Once I wrapped my mind around this, I started to understand something. Manifolds are just graphs with many vertices. Fourier analysis studies the eigen-decomposition of the laplacian on a graph, and is used to solve heat, wave and dispersion equations. Stokes theorem (…

> Only when you lose discreteness or compactness things start to get nasty. But this is just a flaw in our current definition of real numbers. What "flaw" are you referring to? Also you're certainly free to use other definitions for real numbers, if you feel they better capture "reality".

The problem I've always had with real numbers is that the vast majority (i.e. uncountably many) of them are not computable, and only countably many of them are computable.

That means that almost every real number, all but a vanishingly small subset, cannot be represented by any means whatsoever. No formulas, no algorithms, nothing. On top of which, they're surprisingly complicated to construct. There's several different ways of doing it, and they're all complicated.

At some point you've got to ask yourself, "are they really even there?" (Of course, those who already have non-Platonic leanings will find that question amusing.) I start to think that maybe we'd be better served by dropping all the non-computable numbers and start doing almost everything in the field of computables.

Re: Why Discrete Math Is Important

#104

Post by jumpman500 »

Verdex_3 wrote: post #94
jumpman500 wrote: post #80

Earlier quoted context omitted.

What? You can make easily make basic statistic and probability about real problems and interesting. Talk about sports. Talk about risks of the stock market and financial planning. Talk about politics/polling. Talk about gambling/poker. Just takes an interesting teacher to make any subject interesting.

Like, I want to believe you that such a thing is easy. But I'm not really convinced by the assertion that it is followed by a non-descriptive blurb. I mean I get what you're saying, "Find what they care about and try to apply statistics to it." However, I don't believe that this process is easy. Sports is a good example of why I don't think this is easy. What exactly is the point of statistics in sports? Predicting w…

Well I'm commenting on the internet Verdex_3. I'm not going to take the time to write out a bunch of interesting statistical examples for you. I wasn't trying to say it's easy to make statistics interesting. Was only trying to refute what I thought that you were asserting; statistics and probability are not interesting to teach. Designing enjoyable, interesting, challenging and fair curriculum is a really hard task to do for any subject...

If you don't believe math can be made interesting I would checkout websites like FiveThirtyEight or youtube channels like numberphile. It's definitely possible to describe statistics or math problems in interesting ways. It's hard to make any class interesting, but any teacher can do it if they work at it hard enough.

Also your moneyball comment makes no sense. All teams operate like the 2002 Oakland A's now, if anything the the movie shows the triump of statistics over bad heuristics.

Re: Why Discrete Math Is Important

#105

Post by dbcurtis »

JoeAltmaier wrote: post #87
dbcurtis wrote: post #82

Earlier quoted context omitted.

Would you concede that the Planck length is a good approximation of the smallest measurable length in the universe?

The change in radius of a black hole when 1 bit of information is added is much smaller than 1 Planck length. The Planck length is just a convenient unit of measure in physics. It has no relevance to limits of space or time at all. Here's an article on the subject: https://www.quora.com/Is-there-anything-smaller-than-a-Planc...

Interesting. I am now better informed.

Re: Why Discrete Math Is Important

#106

Post by dorgo »

e12e wrote: post #78
onychomys wrote: post #65

Even if we don't teach a single day of number theory, I think we can all agree that modern society would be better if everybody had to have a semester of basic probability or statistics as part of their education.

You propose we stop teaching children to count? That two comes after one, is one more than one etc? I don't think we can get away from all discreet math... ;-)

Just pretend the numbers are real :P

Re: Why Discrete Math Is Important

#107

Post by Chris2048 »

ChrisLomont wrote: post #101
Chris2048 wrote: post #67

Earlier quoted context omitted.

"not known to be discrete" does not imply "It's not unreasonable that there are discrete and continuous aspects to the universe"; it is not known that anything is continuous either.

The theories that best model every known experiment are continuous. General relativity models large scale phenomena to incredible precision, and is continuous. Predictions made by it around 100 years ago are still being tested and found true, such as gravitational waves. The Standard Model, which models everything else, is continuous. A specific part of it, QED, is the most accurate theory known, agreeing with experi…

Other leading theories are non-continuous. LGQ example is an active area of research.

> Every physics theory that we use to explain the universe is continuous

Are you suggesting thete are no discrete models?

Any discrete model may be similar to leading continuous models, so the explanatory power of both isn't relevant unless it can only be produced by continuous models.

Re: Why Discrete Math Is Important

#108

Post by enriquto »

gjm11 wrote: post #68
enriquto wrote: post #29

Discrete math is important because the universe is discrete. Continuous math is an approximation that sometimes, but not always, is rather convenient. Once I wrapped my mind around this, I started to understand something. Manifolds are just graphs with many vertices. Fourier analysis studies the eigen-decomposition of the laplacian on a graph, and is used to solve heat, wave and dispersion equations. Stokes theorem (…

I am intrigued by your ideas and wish to subscribe to your newsletter. How does Stokes' theorem in a discrete setting just amount to associativity? (I wondered about the sort of discrete differential geometry found e.g. here https://www.cs.cmu.edu/~kmcrane/Projects/DDG/paper.pdf and here https://arxiv.org/pdf/math/0508341.pdf but in that setting the situation seems to be more "Stokes' theorem is true by definition".)

I am intrigued by your ideas and wish to subscribe to your newsletter.

Lol, this is not the first time that I am mocked here :)

How does Stokes' theorem in a discrete setting just amount to associativity?

Manifolds are modeled by graphs, and calculus on manifolds becomes linear algebra using the matrices naturally associated to these graphs.

Consider a graph with n vertices and m edges.

The most important matrix is the oriented incidence matrix B, of size mxn, that has a single +1 and a single -1 on each row, indicating the vertices connected by the corresponding edge.

Scalar fields := functions defined over the vertices = vectors of R^n

Vector fields := functions defined over the edges = vectors of R^m

When you interpret matrices as linear operators:

    B     : R^n -> R^m is the gradient operator
    -B'   : R^m -> R^n is the divergence operator
    -B'.B : R^n -> R^n is the laplacian
A subset of the vertices is given by a binary vector M \in R^n. The integral of a scalar field f over M is M'.f

The outwards boundary of a subset M is -B.M. The flux of a vector field F through this boundary is (-B.M)'.F

Stokes theorem is thus the trivial identity (-B.M)'.F = M'.(-B'.F)

(I use a dot for matrix products because the star breaks the formatting. You can also define the divergence without the minus sign, but I like my laplacians to be negative-definite, it feels weird otherwise.)

Re: Why Discrete Math Is Important

#109

Post by therealdrag0 »

jumpman500 wrote: post #80
Verdex_3 wrote: post #73

Earlier quoted context omitted.

Not really. You have to find a way to make the math real to your students or else it becomes just another exercise of "what set of words do I need to say in order to make the teacher happy". At least in my experience, most learning seems to be either incidental OR some sort of vestigial residue of the social component of making the system happy.

What? You can make easily make basic statistic and probability about real problems and interesting. Talk about sports. Talk about risks of the stock market and financial planning. Talk about politics/polling. Talk about gambling/poker. Just takes an interesting teacher to make any subject interesting.

Talk about medical screens and their interpretation (eg., https://www.youtube.com/watch?v=Ql2jEJ-6e-Y)

Re: Why Discrete Math Is Important

#110

Post by enriquto »

woopwoop wrote: post #64
enriquto wrote: post #29

Discrete math is important because the universe is discrete. Continuous math is an approximation that sometimes, but not always, is rather convenient. Once I wrapped my mind around this, I started to understand something. Manifolds are just graphs with many vertices. Fourier analysis studies the eigen-decomposition of the laplacian on a graph, and is used to solve heat, wave and dispersion equations. Stokes theorem (…

>Manifolds are just graphs with many vertices. Okay, I'll bite. How? What is the definition of the tangent space? Dimension?

the tangent space is the set of edges

vector fields (sections of the tangent bundle) correspond to real-valued functions defined on edges

dimension is always 2 ;)

if you want higher dimension you have to consider higher-dimensional cliques beyond edges (that are 2-cliques): triangles, tetrahedra, and so on. But very often this is not necessary, even when discretizing 3d stuff. For example, for Poisson equation, and the associated classical pde, you only need the laplacian, which acts on functions, regardless of the dimension.

Post reply on HN