Wikipedia:Reference desk/Archives/Mathematics/2017 May 7

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 7

Infinitesimal distances in Taxicab distance

If I measure the diagonal distance of a unit square I have a distance of 1.4, if instead I use the Taxicab distance, then the distance is 2. Now suppose I make the lines segments of the taxicab zigzag smaller and smaller - at some point they will look just like a diagonal.

I assume that even as the segments approach zero length they will still always add up to 2, yet my feeling is that they "should" eventually be indistinguishable from the diagonal they look like with a distance of 1.4.

So what am I missing, why doesn't the length approach 1.4 as the segments get smaller? Ariel. (talk) 02:49, 7 May 2017 (UTC)

The arc length of a limit of a sequence of curves is not necessarily the same as the limit of the sequence of arc lengths of each individual curve. Your observation serves as a counterexample of that. No matter how finely you draw the zigzag, each individual sawtooth will overestimate the part of the diagonal it covers by a factor of √2. --Deacon Vorbis (talk) 03:44, 7 May 2017 (UTC)

The "feeling" that they should be indistinguishable is based on experiences in the real world, but the construction you are describing (a stairstep with arbitrarily narrow steps) is a mathematical abstraction and does not exist in the real world. So your instinct does not apply. --76.71.6.254 (talk) 04:35, 7 May 2017 (UTC)

It works for calculating area under a curve - the arbitrarily narrow stairsteps eventually do add up to the proper area. But it doesn't work here. Ariel. (talk) 07:53, 7 May 2017 (UTC)

Maybe not, depending on what you mean. For calculating area, we cut the region into small pieces, take an approximation of each piece, add up the approximations, and take a limit. This works when the errors in the small approximations get small "fast enough". For arclength, the same sort of restriction applies: you have to cut things into small pieces in a way that the net error is getting smaller. Because your approximation is bad to each small piece, you don't successfully reduce error here, so taking a limit doesn't help. --JBL (talk) 14:12, 7 May 2017 (UTC)

You might be interested in curves such as the Koch snowflake which have infinite length. Dbfirs 08:05, 7 May 2017 (UTC)

See also Wikipedia:Reference desk/Archives/Mathematics/2014 September 3#Why is this surface area approximation for a solid of revolution erroneous?, where I wanted to get to the bottom of what was essentially a higher-dimensional analogue of this fallacy committed by some classmates.--Jasper Deng (talk) 10:57, 7 May 2017 (UTC)

Dependency of events

Hi,

Suppose we have a directed graph, where the in-degree of each vertex is $d$, and also, the out-degree of each vertex is $d$. Now, each vertex is colored in one of the colors $1,..,k$ (uniformly and independently). For each vertex $v$ we denote $A_{v}$ to be the event that $v$ don't have an out neighbor with the same color as $v$.
My question is: Given a vertex $v$, what is (at most) the size of the group $\{u|A_{v}\ depends\ on\ A_{u}\}$ ?
Thanks in advance — Preceding unsigned comment added by 31.168.108.114 (talk) 10:10, 7 May 2017 (UTC)

This is just a crude upper bound... $A_{v}$ gives us information about a set of $d+1$ vertices ($v$ and its out-neighbors). It gives us no information about any singleton within that set, however. So in order for $A_{u}$ to depend on $A_{v}$, the $d+1$ vertices that $A_{u}$ cares about must contain at least 2 vertices from those that $A_{v}$ cares about.

There are $d+(d-1)d$ incoming edges to this set, apart from those originating at $v$. We can spend $d$ of them on $v$'s out-neighbors. That leaves $(d-1)d$ to spend on other vertices, giving us a total of $d+(d-1)d/2+1$ vertices $u$ where $A_{u}$ potentially depends on $A_{v}$ (the +1 is for $v$ itself).--2406:E006:2C7:1:5C17:D8B:F83:203E (talk) 11:50, 7 May 2017 (UTC)

Prime factorization

We know that the worst case for trial division is when n=p^2. Therefore p=sqrt(n). Assuming the worst case and naïve trial division(all integers), the time is only sqrt(n), and therefore is sub-linear. So why is factorization so hard?32ieww (talk) 16:26, 7 May 2017 (UTC)

Measurements of computational complexity of time are based on the number of digits or bits of the input, not the actual size of the number itself, i.e. log(n) for a numerical input, n, with the log being to the base of the number. Sqrt(n) >> log(n). Bubba73 ^{You talkin' to me?} 16:38, 7 May 2017 (UTC)

• Or to put it another way, if the number of input digits in the number to be factored is d, the number is between $10^{d-1}$ and $10^{d}.$ So the square root of that, which is the number of potential factors that you would have to try by your brute force method, is at least ${\sqrt {10^{(d-1)}}}=10^{(d-1)/2},$ which is exponential in d. Loraof (talk) 19:07, 7 May 2017 (UTC)
• I don't think it's fair to say that complexity is measured in terms of the number of bits of n. In any case, $O({\sqrt {n}})$ is pretty good if $n\approx 10^{10}$ or even $10^{20}$, but if you're trying to factor a 100-digit number, then that's still on the order of $10^{50}$ operations, which would take all the computing power on Earth longer than the age of the universe to complete. --Deacon Vorbis (talk) 20:14, 7 May 2017 (UTC)

In what sense is it "not fair"? Complexity is nearly always measured in terms of the size of the input, and this setting is not exceptional. --JBL (talk) 20:26, 7 May 2017 (UTC)

The first sentence of time complexity says that is how it is done (the size of the input). Bubba73 ^{You talkin' to me?} 21:38, 7 May 2017 (UTC)

Pascal's triangle and primes

Is it true that all the numbers in a prime-numbered row of Pascal's triangle are divisible by said prime number except for the 1s at the ends?32ieww (talk) 16:35, 7 May 2017 (UTC)

Yes, it is true. Bubba73 ^{You talkin' to me?} 16:43, 7 May 2017 (UTC)

By Pascal's triangle#Binomial expansions, element i of row n is $a_{i}={n \choose i},$ which equals ${\frac {n!}{i!(n-i)!}}.$ If n is prime, it does not divide the denominator (except for the extreme values of i) but does divide the numerator, so it remains in the expression after the division; so your answer is yes. Loraof (talk) 16:54, 7 May 2017 (UTC)

Polyform names

We know there are 11 kinds of polyforms in 2 dimensions (plus their topological equivalents.) They are:

• Polyiamond = equilateral traingles
• Polyomino = squares
• Polyhex = hexagons
• Polyabolo = 45-45-90 triangles
• Polydrafter = 30-60-90 triangles
• Polypon = 30-30-120 triangles
• Polyrhomb = 60-120-60-120 rhombuses
• Polykite = 90-120-90-60 kite
• Polycairo = 120-120-90-120-90 pentagon
• ????????????? = 120-120-120-90-90 pentagon
• ????????????? = 120-120-120-120-60 pentagon

Any web sites that reveal names of these 2 kinds of polyforms?? MathWorld doesn't. Georgia guy (talk) 17:54, 7 May 2017 (UTC)

You're assuming there's enough interest in them for someone to have named them. From a survey of OEIS, it looks like polynominoes have attracted the most research, polyhexes and polyiamonds about tied for second, with other forms trailing far behind. Of more interest are polysticks. There are some entries in the OEIS on "polydominos" and other forms not on your list. The standards for inclusion in the OEIS are pretty low though; there's one entry on "polydudes", but the reference given doesn't have a definition, so what exactly a polydude is is speculative. --RDBury (talk) 04:32, 8 May 2017 (UTC)

What is the difference between these and a figure that can be tiled? For instance why are most of the Pentagonal tilings not included in the article. Dmcq (talk) 08:18, 9 May 2017 (UTC)