Wikipedia:Reference desk/Archives/Mathematics/2008 November 8

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.

November 8

How does this work?

http://www.youtube.com/watch?v=-Jn18MBeibA —Preceding unsigned comment added by 82.124.214.224 (talk) 01:20, 8 November 2008 (UTC)

That's just the distributive law. Each column comes from, say, the 100s place of one factor and the 10s of the other, or the 10s of the one and the 100s of the other (because you went down one set of lines for one factor but up one set for the other), so that's the 1000s column. It's not so useful-looking a method when you have 9s in the numbers. --Tardis (talk) 04:14, 8 November 2008 (UTC)

It's just long multiplication for people that can't multiply single digit numbers together and add... --Tango (talk) 14:04, 8 November 2008 (UTC)

A quantity linked to a graph.

Since I see there are graph theory experts around, I'd like to ask : is this quantity linked to a (say finite) graph G=(V,E) known to some of you, or does it tell you something?

$c(G):=\max {\Big \{}\sum _{(i,j)\in E}x_{i}x_{j}\ :x_{i}\geq 0,\ \sum _{i\in V}x_{i}=1{\Big \}}$.

Or what can you say about the corresponding maximizing distribution of weights? The optimality conditions at a maximum reads: a maximizing distribution $\{x_{i}\}_{i\in V}$ is such that the sum of weights around any vertex v is always less or equal 2c(G), with equality whenever $x_{v}>0$. Thanks. --PMajer (talk) 11:11, 8 November 2008 (UTC)

Suppose you randomly and independently selected two vertices from the graph using the same probability distribution, the quantity concerned represent the probability that the two vertices are adjacent. The problem then becomes to find the probability distribution that will maximize the probability of the event above. (Technically, there is problem for the order of selection, whether the graph is simple or has loop, multiple edges, etc) Notice that we can represent the problem by adjacency matrix: denote the probability distribution by $v=(x_{1}x_{2}\cdots x_{n})$, then we want to maximize $vAv^{T}$, subject to $(11\cdots 1)v^{T}=0$ and $v\geq 0$. I guess we can brute force it using multivariable calculus, say, Lagrange_multipliers. -- Lemontea (talk) 05:52, 9 November 2008 (UTC)

I don't have much in the way of an answer, but I think it's worth pointing out that this is closely related to finding dense subgraphs such as cliques in the given graph. Because if you use x_i as the probabilities of choosing two vertices independently, the sum being maximized is the probability that this choice gives you an edge. If you have a subgraph in which the proportion of edges to non-edges (including non-self-loops) is p, then you can achieve a value of p for c(G) by setting the vertex weights x_i uniformly within this subgraph and zero outside it. —David Eppstein (talk) 23:06, 9 November 2008 (UTC)

Thanks a lot... Nice interpretation. As to Lagrange multipliers, it seems all they give is the property I wrote above. Another fact I noticed: if there is a graph map $h:G\to G'$, then $c(G)\leq c(G')$.--PMajer (talk) 13:21, 10 November 2008 (UTC)

By the way, I assume that you're mostly interested in the case where $G$ has no self-loops, since (as a corollary to David Eppstein's remark) if $(i,i)\in E$ for some $i\in V$, a maximum of $c(G)=1$ is trivially attained by setting $x_{i}=1$ (and $x_{j}=0$ for all other $j\in V$). —Ilmari Karonen (talk) 17:42, 10 November 2008 (UTC)

Is L really a splitting field?

Hello.

Regarding the splitting field L of Splitting_field. 2^(1/3) is a member of this field. 2^(1/3)*2^(1/3)=2^(2/3), so 2^(2/3) should also be a member of the field L. However, as L has been defined right now, this is not the case.

Or am I missing something here? Can it somehow be generated by the other members of L that I'm missing?

Thanks! PureRumble (talk) 13:26, 8 November 2008 (UTC)

It should. I believe a basis of L/Q will be $\{1,2^{1/3},2^{2/3},\zeta _{3},\zeta _{3}2^{1/3},\zeta _{3}2^{2/3}\}$. Note that $\{1,\zeta _{3},\zeta _{3}^{2}\}$ is linearly dependent, I think that’s where the article messed up. It should be something like

$L=\{a+b\omega _{2}+c{\sqrt[{3}]{2}}+d{\sqrt[{3}]{2}}\omega _{2}+e{\sqrt[{3}]{4}}+f{\sqrt[{3}]{4}}\omega _{2}\,|\,a,b,c,d,e,f\in \mathbb {Q} \}$

Where I used $\zeta _{3}=\omega _{2}$ GromXXVII (talk) 13:49, 8 November 2008 (UTC)

I agree. They've included an unnecessary square of the primitive cube root of unity and not included the necessary square of the cube root of two. I'm not sure it's a good idea to just write it out like that without any clue about where it's come from, though. It should start something like: $L=\mathbb {Q} ({\sqrt[{3}]{2}},\zeta _{3})=\{\Sigma _{i,j=0}^{2}a_{i,j}{\sqrt[{3}]{2}}^{i}\zeta _{3}^{j}|a_{i,j}\in \mathbb {Q} \}$ and then write it out with all the linear dependence taken into account (with explanation). --Tango (talk) 14:01, 8 November 2008 (UTC)

Now, what disappoints me is that 48 hours have passed and none of you wikipedia users have fixed the article... tsssk, tsssk, tsssk :-P. Don't look at me, can't handle the syntax for inserting such fancy math formulas you can (and I'm gonna close my eyes for being able to copy it from the window where I'm writing this right now and past it into the article) ;-) PureRumble (talk) 10:57, 10 November 2008 (UTC)

I’ve been keeping my eye on the article, I expected the OP was going to and so didn’t want to go and change it out from under him. It’s now correct I believe but could use some TLC I can’t provide at the moment. GromXXVII (talk) 12:09, 10 November 2008 (UTC)

A number

Can you say anything special about the number 4,052,739,537,880? You are officially the masters of the universe if you find out how I came up with it, but maybe there's something else too. --91.145.88.191 (talk) 15:45, 8 November 2008 (UTC)

It's a Fibonacci number. Wikiant (talk) 16:00, 8 November 2008 (UTC)

No it's not. It's one less than the 62nd Fibonacci number. Algebraist 16:26, 8 November 2008 (UTC)

But it is a sum/difference of fibonacci numbers.. I hadn't realized that before, but it's quite clear now when somebody said it. Thanks --91.145.88.191 (talk) 18:00, 8 November 2008 (UTC)

The first entry that comes up when you google the number had that as a fibonacci number. Google is the master of the universe but sometimes gets it wrong :) I guess they calculated it using floating point and it rounded down. Seeming The Math Factor Podcast raised the question of the smallest ungoogleable number. Dmcq (talk) 19:04, 8 November 2008 (UTC)

The second Ghit was from a reliable source, though, so I went straight to that and ignored all the others. Algebraist 20:24, 8 November 2008 (UTC)

It's three more than a prime. —Tamfang (talk) 03:39, 9 November 2008 (UTC)

We might be able to find some other relevance to the number if you told us how you came up with it in the first place. Playing 20 questions with Google is not what this desk is for. « Aaron Rotenberg « Talk « 08:19, 9 November 2008 (UTC)

This has to do with a programming competition so even if it's unlikely anyone on it will read this I won't tell more before wednesday. Anyway, you don't have to bother to think more of this anymore, unless you really want, I don't believe there's much else than the fibonacci thing. --91.145.88.191 (talk) 12:31, 9 November 2008 (UTC)

Its prime factorisation is 2³x5x11x31x61x1087x4481, but the only thing that OEIS comes up with in relation to a decent subset of those is the factorisation of Fibonacci numbers, which appears to be a side-effect of the discussion above. Confusing Manifestation(Say hi!) 03:18, 10 November 2008 (UTC)

Ok, it was the amount of numbers between 0 and 10¹⁸ that have no ones next to other ones (sorry my english) in their binary presentation. My ip might have changed a little. --194.197.235.221 (talk) 15:22, 13 November 2008 (UTC)

No wonder it's close to a fibonacci number then. – b_jonas 19:28, 14 November 2008 (UTC)