User aaron meyerowitz - MathOverflow

Answer by Aaron Meyerowitz for Why don't more mathematicians improve Wikipedia articles?

2013-05-22T13:34:36Z

Some articles have contributors who are very possessive. It is amazing and impressive that the Wikipedia model works so well. I find it a great first pass on a variety of topics. Often I feel no need to look further. Other times I do. The price of that is that contributing is not worth it unless one is willing to watch the page and decide when to engage and when to let it go.

Answer by Aaron Meyerowitz for Sequences equidistributed modulo 1

2013-05-19T08:59:02Z

Consider all possible pairs $(a,s_n)$ of a positive irrational $a$ and an integer sequence $s_n$ with exponential growth. It seems likely (maybe even easy to show) that it is almost always true that the sequence of fractional parts $[r_n]=\{s_na\}|_{n \in \mathbf{N}}$ is equally distributed in $[0,1).$ For example for any fixed sequence $s_n$ (or even all the sequences $b^n$) the set of appropriate $a$ will have density $1$.

You've already rejected this, but take $s_n=10^{n^{2}}.$ then given a desired sequence $r_n^'$ in $[0,1)$ we can easily describe an explicit $a$ such that $|\{s_na\}-r_n^'| \lt 10^{1-2n}$ (use the first $2j-1$ digits of $r_j'$ followed by the first $2j+1$ of $r^'_{j+1}$ etc. for $j \ge 1$.)

You will probably be as displeased with this, but I'll mention it anyway: Pick any positive irrational $a$ you wish and any desired sequence $r_n^'$ in $[0,1).$ Then we can also pick an integer sequence $s_n$ one term at a time so that for each $n$, $|\{s_na\}-r_n^'| \lt 10^{-n}$ and $\frac{s_1}{s_n} \lt \frac{s_2}{s_n} \lt \ldots \lt \frac{s_{n-1}}{s_n} \lt10^{-n}$: Suppose $s_{k-1}$ has been determined and consider in order $s_k=10^ks_{k-1},1+10^ks_{k-1},2+10^ks_{k-1},\cdots .$ From the theorem of Weyl, you are sure to eventually arrive at a choice with $\{s_ka\}$ differing from $r^'_k$ by no more than $10^{-k}.$

Answer by Aaron Meyerowitz for Blue and red balls puzzle

2013-05-16T18:57:19Z

You are asking for $f(n,n)$ where $f(r,b)$ is the expected number of balls at the end starting with $r$ red and $b$ blue.

Since

$f(0,m)=f(m,0)=m$ and
$f(r,b)=\frac{b}{r+b}f(r-1,b)+\frac{r}{r+b}f(r,b-1)$ when $r,b\gt 0$,

it is easy to find these values which will all be rational and hence not exactly $n^{\frac34}.$

$f(10,10)=\frac{3950111866161571}{691165343232000} \approx 5.7151$ which is close, but of course not equal to $10^{\frac34} \approx 5.6234.$

I see that this is an active question elsewhere and most votes do seem to be for $O(n^{3/4})$ so I'll just say that $f(200,200)=55.603$ and $200^{3/4}=53.183$ so $n^{3/4}$ looks right.

Answer by Aaron Meyerowitz for Another colored balls puzzle (part II)

2013-05-14T23:21:12Z

LATER Concerning procedure 1: We know that the expected number of steps is greater than $2^{n-1}.$ However it appears that perhaps the expected number of steps is $2^{n-1}(1+\frac{1+o(n)}{n}).$ There will be a stage (after at least $n-2$ steps) at which there are $n-1$ balls of the same color and $1$ of another color. As has been elegantly proved, from this point the expected number of steps until all balls are the same color is exactly $2^{n-1}-1.$ This provides a lower bound and, in fact, a surprisingly good one. For each value of $n$ from $3$ to $6$ I did $50,000$ trials and for each value of $n$ from $7$ to $13$ I did $5000$ trials of the first procedure for $n$ balls initially with $n$ distinct colors. Here are the rounded averages

$[3, 4], [4, 10], [5, 22], [6, 45],[7, 88], [8, 172], [9, 322], [10, 610], [11, 1182], [12, 2388], [13, 4548]$

In all cases this is less than $2^{n-1}(1+\frac{3}{n})$ and for the last four cases less than $2^{n-1}(1+\frac{2}{n}).$

even later The exact expectations for $n$ up to $20$ found by Karl support this. If $a_n$ is the expected number of steps to get from $n$ balls with $n$ different colors to all the same color and $a_n=2^{n-1}(1+\frac{b_n}{n})$ then we have these values for $b_n:$

$ [5, 2.495], [6, 2.752], [7, 2.752], [8, 2.516], [9, 2.364], [10, 2.140], [11, 1.925], [12, 1.741],$$ [13, 1.600], [14, 1.488], [15, 1.404], [16, 1.341], [17, 1.294], [18, 1.258], [19, 1.231], [20, 1.210]$

EARLIER Consider the related problem of just two colors of balls, white and black (wlog at least as many black as white.) This will give lower bounds since the given problem will eventually have two colors of balls before it has just one. Also, we can split the many colors into two groups (light and dark) and follow the process. This simplification amounts to not counting the steps that involve two colors from the same group. The expected number of steps to get from $1$ white and $b$ black to all the same color has been shown to be $2^b-1=2^{n-1}-1$ where $n=w+b$ is the total number of balls. If the number of white balls is at least $2$ of a total of $n$ then the expected number of steps appears to be roughly $2^{n-1}(1+\frac{1}{n}+\frac{w^2-w}{2n^2})$

Let $f(w,b)$ be the expected number of steps to get from $w$ white and $b$ black balls to a situation with all balls of the same color. Also, let $g(w)$ be $f(w,b)=f(w,n-w)$ as a function of $n=b+w.$ As Douglas observed for $b \le 100$ and Uri proved for all $b$, $f(1,b)=2^b-1$ (i.e. $g(1)=2^{n-1}-1$) It appears that $f(b,b)=2^{2b-1}(1+o(b))$ of course $f(b,b) \gt f(1,2b-1)=2^{2b-1}-1$ so almost all the time is taken up trying to get past the final step. Some numerical data is at the end.

Clearly

$f(0,b)=0$
for $w \gt 0$, $f(w,b)=1+\frac{w}{w+b}f(w-1,b+1)+\frac{b}{w+b}f(w+1,b-1)$ so
$f(b,b)=1+f(b-1,b+1)$ and $f(b-1,b)=\frac{2b-1}{b-1}(1+f(b-2,b+1))$.

For fixed $n=b+w$ this system of equations is sufficient to find all the values $f(w,n-w)$

formulas

The first two observations above are
- $g(0)=0$
- For $w \gt 0$, $g(w)=1+\frac{w}{n}g(w-1)+\frac{n-w}{n}g(w+1)$

This is sufficient to find the ratio of each of the $g(w)$ for fixed $w$ to $g(1)$ which we now know to be $g(1)=2^{n-1}-1.$ However (since I wrote this before I knew a proof of the value for $g(1)$) let us just define $g(1)=Z=Z(n).$ Then the first few equations are

$g(0)=0$

$g(1)=Z$ (by fiat) but also

$g(1)=1+\frac{n-1}{n}g(2)+\frac{1}{n}g(0)$ so $g(2)=\frac{n}{n-1}Z-\frac{n}{n-1} $

$g(2)=1+\frac{n-2}{n}g(3)+\frac{2}{n}g(1)$ so with a little work: $g(3)=\frac{n^2-2n-2}{(n-1)(n-2)}Z-\frac{n(2n-1)}{(n-1)(n-2)} $

$g(4)=\frac{n(n^2-5n+8)}{(n-1)(n-2)(n-3)}Z-\frac{n(3n^2-7n+8)}{(n-1)(n-2)(n-3)} $

$g(5)=\frac{n^4-9n^3+28n^2-32n+24}{(n-1)(n-2)(n-3)(n-4)}Z-\frac{n(4n^3-21n^2+47n-18)}{(n-1)(n-2)(n-3)(n-4)}$

This can be carried as far as desired. I satisfied myself that

$$g(w)=\frac{n^{w-1}-(\binom{n}{2}-1)n^{w-2}+o(n^{w-2})}{n^{w-1}-(\binom{n}{2})n^{w-2}+o(n^{w-2})}Z+o(n) \approx (1+\frac{1}{n}+\frac{w^2}{2n^2})Z.$$ This seems to agree well with the numerical calculations.

Numerical Results

The exact values of $f(b,b)$ for $1 \le b \le 19$ are

$1,8,37,{\frac {448}{3}},{\frac {1753}{3}},{\frac {11416}{5}},{\frac { 134471}{15}},{\frac {3713536}{105}},{\frac {4900661}{35}},{\frac { 35008504}{63}},{\frac {695863087}{315}},{\frac {10155396928}{1155}},{ \frac {121367279443}{3465}},$${\frac {898500004936}{6435}},{\frac { 1672315989611}{3003}},{\frac {100087214575616}{45045}},{\frac { 399474183415387}{45045}},{\frac {430350607437304}{12155}},{\frac { 15466270252272383}{109395}}$

and the base $2$ logs of these numbers are $0., 3., 5.20946, 7.22239, 9.19065, 11.1568, 13.1300, 15.1101, 17.0952, 19.0840, 21.0750,$$ 23.0678,25.0619, 27.0570, 29.0529, 31.0491, 33.0461, 35.0432, 37.0408$

For $20$ balls the exact expected number of steps to get to all the same color is

$555690+\frac{29}{63}={\frac {35008504}{63}},{\frac {35008441}{63}},{\frac {11669408}{21}}, {\frac {3889749}{7}},{\frac {1666984}{3}},{\frac {5000563}{9}},{\frac {4999360}{9}},{\frac {4994503}{9}},551880,524287,0.$

So $f(1,19)=2^{19}-1=524,287$ steps expected for a $1/19$ white/black split. An additional $27,593$ expected steps for $f(2,18)$ an $18/2$. In more detail the increases are $1., 3.44444, 7.66667, 17.0952, 43.2222, 133.667, 539.667, 3064.78, 27593, 524287 $ are the expected numbers of additional steps. So $f(10,10)$ is (of course) one more than $f(9,11)$ which is $3.44$ more than $f(8,12)$ etc.

Answer by Aaron Meyerowitz for Number of Distinct Sums of Integers

2013-04-29T18:00:40Z

Here is a possible formulation of your question: A multiset is a list $S$ of positive integers $x_1 \le x_2 \le \cdots \le x_k.$ The size is $k=|S|$ and the total is $t=\Sigma_{x \in S}x.$ Call $S$ a $(k,t)-$multiset (which could also be called an unordered partition of $t$ into $k$ positive parts.) There are $2^k$ sums of some all or none of the $x_i$ and, as you say, the number of distinct sums could be as high as $2^k$ ( provided that $t \ge 2^{k}-1$) and as small as $k+1$ (provided that $t$ is a multiple of $k$).

Since the number of $(k,t)-$multisets is finite, what can be said, for fixed $k,t$, about the average number of distinct sums for a "randomly" chosen $(k,t)-$multiset.

There are still choices of what is meant by random. We could write each possible multiset on a card and pick one at random: then $13,13,13,13$ would be as likely as $3,10,13,26$ for $k,t=4,52.$ Or, you could roll a fair $4$-sided die $52$ times, see how often each face comes up and just use the multiset of those 4 counts ( you would either need to start over in the unlikely event that some count is zero or else roll $48$ times and start each count at $1$.). In this second model $5,8,13,26$ is twenty four times more likely than $13,13,13,13$

Later: You have now clarified that you are particularly interested in $(k,2^k+r)$ designs where $r$ is "small". I don't know if you are thinking about $r=3$ or $r=3k$ or $r=k^3.$ Even for $r=3$ I don't think that explicitly generating all multisets would be feasible for $k=10$ (or something like that) I can see a possible opening for impressive probability and statistics arguments by those expert in the field. It am thinking about fixing $k$ and increasing $t$ so perhaps that is not so much your interest, however maybe these thoughts would be of interest:

For $A \subseteq \{1,2,\cdots,k\}$ let $\Sigma_A=\Sigma_{i \in A}x_i.$ Perhaps you want to consider what the set $\mathcal{E}_S=\{(A,B) \mid \Sigma_A=\Sigma_B\}$ could look like for a particular multiset $S$ of values. Certainly if $(A,B)$ is in $\mathcal{E}_S$ with $A,B$ disjoint so are $(A \cup C,B \cup C)$ for any of the $2^{k-|A|-|B|}$ sets disjoint from both. That is a special case of $(A \cup A',B \cup B') \in \mathcal{E}_S$ when the unions are disjoint and $(A,B)$,$(A',B')$ both are.
For $t \lt \binom{k+1}{2}$ there are forced to be solutions of $x_i=x_j$ (with $i \ne j$ of course) each of which leads to $2^{k-2}$ other equal sums as just commented. For $t \lt 2^k-1$ we have $\mathcal{E}_S \ne \emptyset.$
How big must $t$ be relative to $k$ in order to have the $x_i$ distinct with probability greater than $ 1-1/k$ ( or some other $1 - \varepsilon$? ) Is it a sharp transition at some critical point?
The comment above about the isolation lemma seems very interesting. If I read it correctly, then if we take $t=mk$ then the least of the $x_i$ is unique of its value with probability exceeding $1-1/m.$ If we take that singleton set out of consideration then the next smallest is again unique of its weight with probability exceeding $1-1/m$ etc. So the expected number of distinct $x_i$ is at least $(1-1/m)k.$
How much larger (I'd guess quite a bit larger) does $t$ have to be in order to make it unlikely that there would be any cases of $x_i+x_j=x_k+x_{\ell}$? The same question if we ask that instead (or in addition) we are unlikely to see $x_i+x_j=x_k?.$ Again the isolation lemma says that for any given partition of the index set $\{1,\cdots,k\}$ or merely family $F$ of subsets of the index set, the $A \in F$ which minimizes $\Sigma_A$ is the only one of its weight with probability exceeding $1-1/m.$ (So it makes sense to restrict $F$ to at least have no member contain any other.)

Well maybe that is far enough with questions I can't answer.

Answer by Aaron Meyerowitz for What is the effect of adding 1/2 to a continued fraction?

2013-04-28T21:06:44Z

Here are some results which suggest that perhaps what happens is neither very simple nor very random. But see the end for a better result.

These are some of the simplest continued fractions and what they lead to. This also tells you what results in simple continued fractions because $r-\frac12$ and $r+\frac12$ have the same continued fraction after the integer part.

The tenth row says that $$r=\frac{1+\sqrt3}{2}=1+\cfrac{1}{2+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{1+\cfrac{1}{2+\cdots}}}}}$$ and $$r+\frac{1}{2}=1+\frac{\sqrt3}{2}=1+\cfrac{1}{1+\cfrac{1}{6+\cfrac{1}{2+\cfrac{1}{6+\cfrac{1}{2+\cdots}}}}}$$

Each line is a number $r$ then the continued fraction of $r$ then the continued fraction of $r+\frac12$$$ \begin {array}{ccc} \frac{1+\sqrt5}{2}&[[1]]&[[2,8]] \\1+\sqrt {2}&[[2]]&[[2],[1,10,1,1]] \\ \frac{3+\sqrt{13}}{2}&[[3]]&[[3],[1,4,14,4,1,2]] \\2+\sqrt {5}&[[4]]&[[4],[1,2,1,3]] \\ \frac{5+\sqrt{29}}{2}&[[5]]&[[5],[1,2,3,1,20,1,3 ,2,1,4]] \\3+\sqrt {10}&[[6]]&[[6],[1,1,1,24,1,1, 1,5]] \\ \frac{7+\sqrt{53}}{2}&[[7]]&[[7],[1,1,1,3,1 ,1,28,1,1,3,1,1,1,6]] \\4+\sqrt {17}&[[8]]&[[8],[ 1,1,1,1,1,7]] \\ \frac{9+\sqrt{85}}{2}&[[9]]&[[9],[1 ,1,1,1,3,2,36,2,3,1,1,1,1,8]] \\ \frac{1+\sqrt{3}}{2}&[[1,2]] &[[1,1],[6,2]] \\ \frac{3+\sqrt{21}}{6}&[ [1,3]]&[[1, 1],[3,4,3,2]] \\ \frac{1+\sqrt{2}}{2}&[ [1,4]]&[[1,1] ,[2]] \\ \frac{5+3\sqrt{5}}{10}&[ [1,5]]&[[1,1],[2,26, 2,2]] \\ \frac{3+\sqrt{15}}{6}&[ [1,6]]&[[1,1],[1,1,4 ,1,1,2]] \\ \frac{7+\sqrt{77}}{14}&[ [1,7]]&[[1,1],[1 ,1,2,8,2,1,1,2]] \\ \frac{2+\sqrt{6}}{4}&[ [1,8]]&[[1 ,1],[1,1,1,2]] \\ \frac{3+\sqrt{13}}{6}&[ [1,9]]&[[1, 1],[1,1,1,42,1,1,1,2]] \\1+\sqrt {3}&[ [2,1]]&[ [3,4]] \\ 1+ \frac{\sqrt{15}}{3}&[ [2,3]]&[[2],[1,3,1,3,1,1]] \\ 1+ \frac{\sqrt{6}}{2}&[ [2,4]]&[[2],[1,2,1,1]] \\ 1+ \frac{\sqrt{35}}{5}&[ [2,5]]&[[2],[1,2,6,2,1,1]] \\ 1+ \frac{2\sqrt{3}}{3}&[ [2,6]]&[[2],[1,1,1,8,1,1,1,1 ]] \\ 1+ \frac{3\sqrt{7}}{7}&[ [2,7]]&[[2],[1,1,1,2,1,2,1 ,1,1,1]] \\ 1+ \frac{\sqrt{5}}{2}&[ [2,8]]&[[2],[1]] \\ 1+ \frac{\sqrt{11}}{3}&[ [2,9]]&[[2],[1,1,1,1,6,1,1, 1,1,1]]\end {array} $$

I also looked at the first few results of the form $[[3,j]]$ which seemed similar. Rational numbers might also be worth a look.

later as Douglas points out. There are patterns which the tables above are just slightly too brief to show.

The continued fraction $[[k]]$ corresponds to $\frac{k+\sqrt{k^2+4}}{2}$ and we have for $k \ge 2$ (and in some cases for $k \ge 1$)

$2k+\sqrt{(2k)^2+1} \hspace{0.5in} [[4k]] \hspace{0.5in} [[4k],[1,1,k-1,1,1,4k-1]]$

$\frac{4k+1+\sqrt{(4k+1)^2+4}}{2} \hspace{0.5in} [[4k+1]] \hspace{0.5in} [[4k+1],[1,1,k-1,1,3,k,16k+4,k,3,1,k-1,1,1,4k]]$

$2k+1+\sqrt{(2k+1)^2+1} \hspace{0.5in} [[4k+2]] \hspace{0.5in} [[4k+2],[1,1,k,16k+8,k,1,1,4k+1]]$

$\frac{4k+3+\sqrt{(4k+3)^2+4}}{2} \hspace{0.5in} [[4k+3]] \hspace{0.5in} [[4k+3],[1,1,k,3,1,k,16k+12,k,1,3,1,1,4k+2 ]]$

Similar things happen for $[[i,k]]$ $i=1,2$ depending on the congruence class $k \mod 4$ for $k$ not too small.

Answer by Aaron Meyerowitz for signs of eigenvalues

2013-04-22T02:49:44Z

Just to build on the answer which Chris gave, one can replace two disjoint copies $K_3$ with two disjoint copies of any graph $G$ (which is not bipartite, just to keep things simple). Let the vertices of $G$ be numbered $0,1,\cdots,v-1.$ Now make two graphs $G_1$ (not bipartite) and $G_2$ (bipartite) with vertex sets $0,1,\cdots,2v-1$ and matrices $A_1$ and $A_2$. For each edge $(i,j)$ of $G$ add edges $(i,j)$ and $(i+v,j+v)$ to $G_1$ and also edges $(i,j+v)$ and $(i+v,j)$ to $G_2.$ With this numbering we have $A_1^2=A_2^2$ so even knowing the exact matrix $A^2$ does not tell you the eigenvalues of $A$.

If the largest eigenvalue of $A^2$ is $\alpha$ with multiplicity $m$ then $A$ has eigenvalue $+\sqrt{\alpha}$ with multiplicity at least $\frac{m}2.$

If we do not allow loops then we do know that the sum (with multiplicities) of the eigenvalues is $0$.

Here are a couple of explicit variations of the example above which easily generalize (in case you don't want disconnected graphs or don't want a purely bipartite graph). If numbered correctly, they also preserve the $A_1^2=A_2^2$ feature (or $A_1^2=A_2^2=A_3^2$ in the second.)

Add a seventh vertex connected to each of the six others. Then the eigenvalues are $[1+\sqrt{7},1-\sqrt{7},2,-1,-1,-1,-1]$ for two copies of $K_3$ but $[1+\sqrt{7},1-\sqrt{7},-2,1,1,-1,-1]$ for $K_6$
Here are three different graphs each with $12$ vertices and every one of the first $6$ connected to every one of the second $6$: For the first and second sets of $6$ vertices put in edges to make two copies of $K_3$ in each OR $K_6$ in each OR $K_6$ for one and two copies of $K_3$ for the other. Then the eigenvalues are $[ 8,-4,2,2,-1^{8}]$ OR $[8,-4,-2,-2,1^4,-1^4 ]$ OR $[8,-4,2,-2,1^4,-1^4]$

Even this second example can be further generalized to give huge sets of graphs all with distinct spectrums but all having the same $A^2$: Take any graph you like, say $H$ with $w$ vertices, Make (lots of) new graphs with $2vw$ vertices by replacing some vertices by $G_1$ from above and others by $G_2$. Replace each edge of $H$ by $(2v)^2$ edges constituting all possible edges between corresponding copies of $G_i$.

Answer by Aaron Meyerowitz for existence of equivalence checking algorithm

2013-04-16T23:19:06Z

Can every positive even integer be written as a sum of two prime numbers? We certainly expect so but do not expect a definitive proof any time soon (or perhaps ever), even though we expect that for all $k$ there is an $N$ so that every even integer greater than $N$ can be expressed as such in over $k$ ways.

Suppose that $X$ always outputs $1$ immediately without even checking the input $i \ge 2$ and $Y$ takes input $i \ge 2$ and outputs $1$ or $0$ according as $2i$ is or is not a sum of two primes, so $Y$ halts for each output in a well behaved bounded time and usually (we expect) quite quickly . Are they equivalent? We don't expect an answer any time soon.

Answer by Aaron Meyerowitz for Lapses of "the early proponents of the doctrine of limits"

2013-04-16T11:00:08Z

I am no expert in the history of Mathematics but I feel I must say the following since no one else has. Of course Euler ( who just had his $17\cdot 18$) did not think that $1 - 1 + 1 - 1 + 1 - 1 +\cdots=\frac12$ in that way.

Let's agree that we know what a complex series is (stick to $\mathbb{R}$ if you wish): essentially it is any "vector " in $\mathbb{C}^{\mathbb{N}}$ with a $\Sigma$ in front (or $+$ signs) to tell us that we are not looking at it as a sequence. The series form a complex vector space. There is a subspace which we would call the "usual" convergent series and we allow ourselves to say things like $\sum 2^{-n}=1$ although we might claim that really we mean that there is a linear transformation $S$ whose domain is the convergent series with range $\mathbb{C}.$ We sometimes symbolically enlarge the range in a familiar way to include $\pm \infty$ to discuss some kinds of "divergence." And of course we also care about the assertion $\sum z^{-n}=\frac{1}{1-z}$ which is unproblematic in the closed unit disk with the exception of two interesting points which deserve further thought. Integrating term by term (a bold move?) suggests that $-\sum \frac{z^{n+1}}{n+1}=\ln{(1-z)}.$ Whatever our qualms about the first series at $z=-1$, the second seems true and it looks like magic. The convergence is slow although there are ways to accelerate it. These methods applied to $\sum z^n$ at $z=-1$ lead to a not unexpected result.

There is a venerable subject of divergent series and "summation" methods for them. Such a method is a linear transformation $T$ which agrees with $S$ on the "convergent" series and perhaps satisfy a few other axioms enjoyed by $S$ (adding a few extra terms changes the sum in the obvious way.) Any method satisfying those requirements and sending $1-1+1-1+1...$ to a real $r$ would have to send it to one with $r=1-(1-1+1-1+\cdots)=1-r$ and hence to $\frac{1}{2}.$

Maybe most mathematicians have no need for the distinction between a convergent series and the number it converges to. I would certainly advise my students to avoid summing divergent series until they had a firm grasp on the usual practices. The perspective of "summing divergent sequences" feels a bit quaint these days but it is a valid subject. The amazing and brilliant things Euler and others did is the reason we now may choose to safely explore have well tamed domains such as analytic continuation of functions of one or more complex variables or regularization as practiced by Quantum Physicists making the mathematical formalism conform to measurements.

I'm not sure how all this connects to the actual question above but I'm not convinced that it is unrelated.

Answer by Aaron Meyerowitz for References on techniques for solving equations with discontinuous functions such as floor and ceiling?

2013-04-16T07:41:23Z

I agree that the Joe Roberts book is a gem. I've bought two copies over the years. I'd buy a third if I could. Here is a link to a scan I leave ethical issues to you, I got this from another MO answer .

That said, the Wikipedia article may cover the same material (but check for yourself). The main reference for that article seems to be the Graham, Knuth, and Patashnik book so that would be more reliable.

There are various easily verified equations and inequalities such as

$$\Big\lceil \frac{m}{n} \Big\rceil=\Big\lfloor \frac{m+n-1}{n}\Big\rfloor=\Big\lfloor \frac{m-1}{n}\Big\rfloor+1$$ (which would give an alternate form to your answer which you might or might not prefer.) Then it is a matter of practice.

Actually I see that that particular page say "then use a geometric arguement" in discussing quadratic reciprocity. The Joe Roberts book does give the arguement.

Answer by Aaron Meyerowitz for Minimize diameter of a tree

2013-04-15T16:08:11Z

It is a real possibility that you will not be able to change the diameter by changing one edge. I think this is an efficient best possible procedure for doing what you can.

Find the diameter and center by repeatedly removing all leaves. Either the diameter is odd and the center is an edge or the diameter is even and the center is a vertex.

When the diameter is odd consider the tree one step before (of diameter 3), if it is anything other than a path you can't decrease the diameter. Otherwise, delete the central edge, this results in two trees of even diameter. Find the center of each and connect those with an edge.

If the diameter is even then there is a central vertex and the tree one step before has diameter 2. If it is a path of length two, delete one of those two edges from the starting tree, then proceed as above, otherwise you again can not decrease the diameter by changing one edge.

Answer by Aaron Meyerowitz for An unfair game involving an odd number of pieces of chocolate

2013-04-11T03:25:01Z

Here is a start of an approach which might yield patterns and results. It can be taken further but it might or might not provide a solution.

In the game as given, suppose the goal is to eat more chocolate than the other player (and the greater the discrepancy the better), and it is your turn. It does not matter how much chocolate you have already eaten nor how much the other has, all that matters is the current value of $\alpha$ and the number of remaining squares.

So let $\alpha$ be any positive integer and play with a pile of $s$ stones. The current player can take $\alpha$ or $\alpha+2$ stones, all as before. When no move is possible the player with the fewest stones pays the player with the most stones the difference.

The value of this game to the current player is $$v(\alpha,s)=\max\Big(\ \alpha-v(\alpha,s-\alpha),\alpha+2-v(\alpha+2,s-\alpha-2)\ \Big)$$ provided $s \ge \alpha+2.$ The other cases are $v(\alpha,\alpha)=v(\alpha,\alpha+1)=\alpha$ and $v(\alpha,s)=0$ for $s \lt \alpha.$

In this language, the question is,

Is it the case that $v(1,s)$ is always positive for odd $s?$

So perhaps finding the value of $v(\alpha,s)$ in general (including even $\alpha$) is as easy. It might also be as easy to describe the optimal move. All this is easy to program so I probably did it correctly. I looked at the cases $1 \le \alpha \le 40$ and $\alpha \le s \lt 23\alpha.$ Here are some general and somewhat less general observations which I only guarantee for those cases (although some are true in general and I believe others to be so.)

It is almost always (but not always) an advantage to go first so the best move is usually to escalate to $\alpha+2$ sometimes keeping $\alpha$ unchanged is better and sometimes they are equally good.
$v(1,s) \gt 0$ with the exceptions $v(1,s)=0$ for $s=6,8,10,12,16,18$ and $v(1,22)=-2$
Of the $18040$ cases considered, $11328$ have $v(\alpha,s) \gt 0.$ It also takes the values $0,-2,-4,-6,-8$ with frequencies $710,2274,2222,1326,180$ respectively but nothing smaller (over that range).
$v(\alpha,2\alpha+r) \gt 0$ with the exceptions that $v(\alpha,2\alpha+r)=0$ for $r=4,5$ and $\alpha \ge 2r$ and also $v(\alpha,2\alpha+r)=-2$ for $\alpha \ge 2r \ge 12$
The smallest observed cases of $v(\alpha,q\alpha+r)=-8$ are for
- $\alpha=33$ and $[q,r]=[10, 6], [13, -7], [16, -16], [18, 12], [21, 11]$
- $\alpha=34$ and $[q,r]=[10, 4], [10, 5], [13, -10], [13, -9], [15, 14], [15, 15], [18, 8], [18, 9], [21, 6], [21, 7]$
The cases observed with $v(\alpha,q\alpha+r) \le 0$ are listed here.
The cases $[\alpha,q,r,v(q\alpha+r)]$ observed which have $v \gt 2\alpha+1$ are $[1, 15, 0, 5], [1, 21, 0, 5], [2, 9, 0, 6], [2, 9, 1, 6], [2, 17, 0, 6], [2, 17, 1, 6], [2, 21, 0, 6], [2, 21, 1, 6]$

Answer by Aaron Meyerowitz for How long can this string of digits be extended?

2013-04-08T23:52:08Z

Following links at the OEIS entry mentioned above takes one in a step or two to this page where there are posts (from 2005) with Maple code and results out to base $23$. The values $N(b)$ for $2 \le b \le 23$ are reported to be

$2, 6, 7, 10, 11, 18, 17, 22, 25, 26, 28, 35, 39, 38, 39, 45, 48, 48, 52, 53, 56, 58$

Note that $N(7) \gt N(8)$ and $N(14) \gt N(15)$ and $N(19)=N(20).$

The ratios $\frac{N(b)}{b}$ are

$1.0, 2.0, 1.75, 2.0, 1.833, 2.571, 2.125, 2.444, 2.5, 2.364, 2.333, 2.692, $$2.786, 2.533, 2.438, 2.647, 2.667, 2.526, 2.60, 2.524, 2.546, 2.522$

Based on the data so far one might feel somewhat safe speculating that $2\lt \frac{N(b)}{b} \lt 3$ provided $b \gt 6.$ As far as I can see, little nothing is known for sure (including that $N(b)$ is finite althoughthat seems highly likely.)

For each fixed value of $b$ there is a tree of possibilities (if we use a formal root node for level $0$.) A node at level $k-1$ has at most $\lceil \frac{b}{k}\rceil$ children. It might (or might not) be worth looking at the distribution of leaf levels.

Answer by Aaron Meyerowitz for The ratio of one digits and all digits in the binary expansions of the square numbers

2013-04-03T23:04:03Z

It look as if quid has given you an answers which is more profound than what I am about to say. However I took the question another way.

The numbers you report suggest that perhaps for any fixed upper bound $N \gt 2$ we have $$ \lim_{c \to \infty}\max_{x \le N}d(x^{2^c}) \rightarrow 0.5.$$ You can restrict attention to odd $x$ since for even $x$ the powers $x^C$ will accumulate a tail of $0$ bits at the end and always have a lower density than that of $\left(\frac{x}{2}\right)^C.$ That the limit (of the max) is $0.5$ seems very plausible to me. Unless I see a reason to think otherwise, I would expect that the binary strings we get will behave like random binary strings of their length (actually we always start and end with a $1$ which increases the density but this effect goes to zero, however it might be more fair to not count those two bits). The chance that a random string will have density over $0.5+\varepsilon$ ( for fixed $\varepsilon \gt 0$) goes to zero as the length increases. If we have $N$ or $\frac{N}{2}$ strings where $N$ is fixed (but the strings are increasing in length together), the probability that any one of them will have density over $0.5+\varepsilon$ will also go to zero. My assumptions here are vague. Say that every time we increase $c$ to $c+1$ we double the lengths of all the strings via random bit generation. I suspect , by the same reasoning, that $$ \lim_{C \to \infty}\max_{x \le N}d(x^{C}) \rightarrow 0.5.$$ And even that the minimum density (for odd $x \gt 1$) goes to $0.5.$ Equivalently, I conjecture that for any fixed odd $x \gt 1:$ $$ \lim_{C \to \infty}d(x^{C}) \rightarrow 0.5.$$

It is interesting to look at what happens for any one given even $x$ (assuming this last conjecture is true for odd $x$.) It is convenient to look instead at the ratio $d'$ of the number of $1's$ to $\log_2(x)$. This will not affect the limit since it changes the denominator by less than $1.$ If $x=2^tz$ where $z$ is odd then $x^C$ and $z^C$ have the same number of bits equal to $1$, so (we speculate, for large enough $C\cdots$ ) about $0.5C\log z.$ But $\log(x^C)=tC+C\log(z)$ so $d'(x)$ would go to $$\frac{0.5C\log z}{tC+C\log z}=\frac{0.5\log z}{t+\log z}.$$ A very few, very small , experiments support the suggestion that this is the correct limit and that the convergence is rapid..

A question I can't easily answer (assuming that the $\max$ does go to $0.5$) is how rapidly does the $\max$ go to $0.5?$ Perhaps it is faster than a random model would suggest. If $y$ had a density $1$ and then we double the length with random bits we would expect a density about $3/4$ (then $5/8$ then $9/16$ etc) but $y^2$ will already have density nearly $1/2.$ That may or may not make any difference if none of our $\frac{N}{2}$ strings have exceptionally high density.

Answer by Aaron Meyerowitz for At what point does Miller-Rabin become faster than trial division?

2013-04-03T13:26:44Z

Maple does the following:

Check a list of small primes directly
Check the gcd with the precomputed number N=2*3*...*97 if gcd is not 1 the number is composite. Otherwise if the number is under $101^2$ it is prime.
Repeat step 2 but with N the product of the 3 digit primes. By this stage two "trial divisions have checked all prime factors under 1000 and given a definitive answer for anything under $1018081=1009^2$
Go on to fancier methods.

I suppose that having 64 or so more precomputed constants and doing gcd with them could check all prime factors under 65536 if desired.

Answer by Aaron Meyerowitz for irreducible polynomials with arithmetic progression coefficients

2013-03-30T20:09:22Z

I've heard from Zhi-Wei Sun that he recently considered this question. In a post a few days ago to OEIS Least integer b>2n+1 such that the numbers written as [1,3,...,2n-1,2n+1] and [2n+1,2n-1,...,3,1] in base b are both prime. He gives the first of what he conjectures are infinitely many bases (for each fixed $n$) with the named property. Other fairly specific conjectures concerning Galois groups, reducibility over $\mathbb{Z}_p$ and the like can be found on that page. Any one of the conjectures would imply that $1+3x+5x^2+\cdots+(2n+1)x^{n}$ is always irreducible over the integers. A similar post a few days earlier than that concerns $1+2x+\cdots+(n+1)x^{n}$ which he would also conjecture is always irreducible over the integers.

Of course there are integer arithmetic progressions such that $f(a,b,n)=\sum_0^n(a+bk)x^k$ does factor (with $a \ne 0$ of course). At least there is $1+x+x^2+\cdots+x^n$ which is irreducible when and only when $n+1$ is prime. A fairly simple minded search over small parameters turns up

$-n+(2-n)x+(4-n)x^2+\cdots+nx^n$ which has $(x-1)$ as a factor (and $(x+1)$ for even $n$) but no other factors up to $n=42$
After some manipulation, the integer quadratic examples can written $s(t-2s)+(t^2-s^2)x+t(2t-s)x^2$ with linear factor $(s+tx)$
One can first work over $\mathbb{Q}$ , stipulate a factor $x-r=x-t/s$ , set $c_{n-1}=1$ and then solve for $c_0,\cdots,c_{n-2}$ such that $(x-t/s)(c_0+c_1x+\cdots+c_{n-1}x^{n-1})=f(a,b,n)$ for $a=c_0-rc_1$ and $b=r+1-c_{n-2}$. The solutions will have $c_i$ rational functions in $r$ with denominator $n+(n-1)r+\cdots+r^{n-1}$. Then one can scale to integer examples.
Perhaps there are nice solutions which are reducible but without a linear factor.

later Here is the solution for degree $5$ from which the pattern becomes clear. Thanks to Joro and Peter for seeing what I did not. The coefficients below are in arithmetic progression with difference $b=-(s^5+s^4t+s^3t^2+s^2t^3+st^4+t^5).$ It is not immediate, but also is not too hard to check that $(s-tx)$ is a factor as $x=\frac{s}{t}$ is a root.

$$\left(5{s}^{5}+4{s}^{4}t+3{s}^{3}{t}^{2}+2{s}^{2}{t}^{3}+s{t}^{4}+0t^5\right)+\left( 4{s}^{5}+3{s}^{4}t+2{s}^{3}{t}^{2}+{s}^{2}{t}^{3}+0st^4-{t}^{5} \right) x$$ $$\ \ +\left( 3{s}^{5}+2{s}^{4}t+{s}^{3}{t}^{2}+0s^2t^3-s{t}^{4}-2{t}^{5}\right){x}^{2} +\left( 2{s}^{5}+{s}^{4}t+0s^3t^2-{s}^{2}{t}^{3}-2s{t}^{4}-3{t}^{5} \right) {x}^{3}$$ $$\ \ \ \ +\left( {s}^{5}+0s^4t-{s}^{3}{t}^{2}-2{s}^{2}{t}^{3}-3s{t}^{4}-4{t}^{5 } \right) {x}^{4}+\left(0s^5-{s}^{4}t-2{s}^{3}{t}^{2}-3{s}^{2}{t}^{3}-4s{t}^{4}-5{ t}^{5} \right) {x}^{5} $$

Answer by Aaron Meyerowitz for Reverse Gauss's Circle Problem

2013-03-31T08:09:14Z

The number of nodes for radius $r$ is $N_r \approx \pi r^2$ so you can invert to $r_N\approx\sqrt{\frac{N}{\pi}}$. If you wanted to derive the squared distance $r^2$ from $N$, you would have trouble but the square roots are bunched together so maybe that is accurate enough. This does leave some amount of uncertainty:

For $r$ from $\sqrt{1098}$ to $\sqrt{1105}-\varepsilon$ (SO $33.136$ to $33.24153$ and even a bit beyond that) we have $N_r=3456$. At $r=\sqrt{1105}=33.24154$ it jumps to $3488$ because there are $32$ points : $[4,33] ,[9,32],[12,31]$ and $[23,24]$ along with all the variations of making one or both negative and/or swapping the order.

So for $N=3456$ we have $\sqrt{\frac{N}{\pi}}=33.167=\sqrt{1100}$, a bit low perhaps. For $N=3488$ we have $\sqrt{\frac{N}{\pi}}=33.3206 =\sqrt{1110.26}$ This is high because $N$ jumps from $3488$ to $3496$ at $r=\sqrt{1108}$ and then jumps again to $3504$ at $r=\sqrt{1109}$

If you use known precise error bounds for the usual problem you could get error bounds for this dual problem but you can't avoid the uncertainty demonstrated above using a uniform formula.

Answer by Aaron Meyerowitz for Which real scalings of the natural numbers approximately accommodate the unbounded powers of a noninteger?

2013-03-26T07:13:14Z

If I am not mistaken, the class $\Lambda$ of positive reals $\lambda$ which you describe is known to be countable and include all positive rationals as well as reals $a+b\sqrt{D} \in \mathbb{Q}\left[\sqrt{D}\right]$ as well as a larger class of algebraic numbers described below. (I'm not sure if this known class is actually all algebraic numbers, but the answer might be easy, one way or the other.) It is conjectured that there are no transcendental numbers in $\Lambda.$ I am not an expert and my answer relies somewhat on claims whose references I did not personally check.

The nice example you give with $\alpha=\Phi=\frac{1+\sqrt{5}}{2}$ comes from an interesting algebraic setting and satisifes stronger conditions than the ones you give. There are theorems and conjectures depending on what conditions one sets. Other quadratic examples are $\alpha=a+\sqrt{D}$ where $(a-1)^2 \lt D \lt (a+1)^2$ and also $\alpha=\frac{a+\sqrt{D}}{2}$ when $a$ is odd, $D$ is congruent to $1$ $\mod{4}$ and $(a-2)^2 \lt D \lt (a+2)^2.$ These are the quadratic Pisot numbers. Note that a power of such a number has the same form, for example $\Phi^{10}=\frac{123+55\sqrt{5}}{2}=\frac{123+\sqrt{D}}{2}$ for $D=5\cdot 55^2=123^2-4.$ More generally, a Pisot number is a real root $\alpha \gt 1$ of a monic integer polynomial $P(x)$ such that all other roots of $P(x)$ lie strictly inside the unit circle in the complex plane. Any Pisot number $\alpha$ satisfies properties similar to $\Phi$ and it may be that they are the only reals which do. Then the $\lambda$ which work for any given (Pisot number) $\alpha$ are all algebraic numbers from the field of $\alpha$. In other words, $\lambda \in \mathbb{Z}[\alpha]$ and $\lambda$ is a root of a polynomial with integers coefficients (possibly not monic). In the quadratic cases this would include all positive numbers $a+b\sqrt{D} \in \mathbb{Z}[\sqrt{D}].$ We can get $\lambda =\frac{a+b\sqrt{D}}{k}\in \mathbb{Q}[\sqrt{D}]$ by replacing $\alpha$ with some appropriate $k\alpha^t$ where $t$ depends on $k$ and the convergence rate. The details here are a bit sketchy but I don't think it would be hard to more precise.

Let me start with the example which will illustrate why Pisot numbers have this property. The golden ratio $\Phi=\frac{1+\sqrt{5}}{2} \approx 1.618$ is one root of $x^2-x-1$, the other being $\overline{\Phi}=\frac{-1}{\Phi}\approx-0.61803$. So $\Phi$ is a Pisot number. $\Phi$ has the nice property that its powers are nearly integers and also are nearly multiples of $\sqrt{5}$.

For example $\Phi^{10}=\frac{123+55\sqrt{5}}{2}.$ The two terms in the numerator are very nearly equal $\Phi^{10}=122.991869\cdots\approx 123$ and $\frac{1}{\sqrt{5}}\Phi^{10}=55.00363\cdots\approx 55.$ One might recognize that $F_{10}=55$ is the tenth Fibonnacci number, The next is $34+55=89$ and $34+89=123.$ As is well known, these properties generalize: $\frac{\Phi^n+{\overline{\Phi}}^n}{\sqrt{5}}=F_n$ while $\Phi^n+{\overline{\Phi}}^n=F_{n-1}+F_{n+1}.$ Since $\overline{\Phi}^n$ goes to zero we can say that $\lim_{n \to \infty}\|\Phi^n\|=0$ and also $\lim_{n \to \infty}\|\frac{1}{\sqrt{5}}\Phi^n\|=0.$ Here $\|x\|$ denotes the distance from the real $x$ to the nearest integer. $\|x\|=|\ x-\lfloor x \rceil \ |.$

In fact $\overline{\Phi}^n$ goes to zero so rapidly that $\sum_1^{\infty}\|\Phi^n\| \lt \infty$ and also $\sum_1^{\infty}\|\frac{1}{\sqrt{5}} \Phi^n\| \lt \infty.$

It is an easy exercise using $\|x+y\| \le \|x\|+\|y\|$ that the statements above hold for $\| \lambda \Phi^n\|$ where $\lambda$ is any real $\lambda=\frac{a}{\sqrt{5}}+b+c\Phi$ with $a,b,c$ integers. I think that we can expand to allowing $a,b,c \in \mathbb{Q}$ if we replace $\alpha=\Phi$ with $\alpha=(k\Phi)^t$ where $k$ is the greatest common divisor of the denominators and $t$ is so large that the convergence to zero of $\left(k\overline{\Phi}^t\right)^n$ is rapid enough to make $\lfloor\ (k\Phi^t)^n \ \rceil=k^n\lfloor\ (\Phi^t)^n \ \rceil$

Consider the following conditions in increasing order of strength which might be satisfied by a pair of reals $\lambda \gt 0$ and $\alpha \gt 1$ with $\alpha$ irrational along, in the first case, with a positive $\epsilon \lt \frac{1}{2}$.

$\|\lambda \alpha^n\| \lt \epsilon$ for all $n$ (or all large enough $n$)
$\lim_{n \to \infty}\|\lambda \alpha^n\|=0$
$\sum_1^{\infty}\|\lambda \alpha^n\|^2 \lt \infty$
$\sum_1^{\infty}\|\lambda \alpha^n\| \lt \infty$

Note that condition 3 would allow $\|\lambda \alpha^n\|=\frac{1}{n}$ while condition 4 would not.

Note also that if $m \lambda$ is the integer multiple of $\lambda$ closest $\alpha^n$ then $m=\lfloor\frac{1}{\lambda} \alpha^n\rceil$ and $\|\alpha^n-m\lambda\|=\lambda\|\frac{1}{\lambda}\alpha^n\|$ so one goes to zero if and only if the other does. This might mean that for the problem as stated I should have said I was describing $\frac{1}{\lambda}$ for any particular $\alpha$ but in the end the set $\Lambda$ is the same.

According to the Wikepedia article (whose sources I have not personally checked)

Only countably many $\alpha$ satisfy condition 2 for some $\lambda$ and vice versa.
If $\alpha$ is real and condition 3 is satisfied then $\alpha$ is a Pisot number and $\lambda$ is an algebraic number in the field of $\alpha.$
If $\alpha$ is algebraic and condition 2 holds then the same conclusion holds.
It is conjectured, but not known, that the condition algebraic can be ommitted.

One could investigate condition 1 either with $\lambda=1$ or some other $\lambda.$ The idea is to leave $\alpha$ indefinite and consider the sequence of integers $m_n=\lfloor\frac{1}{\lambda}\alpha^n \rceil.$ Each choice limits the interval which could contain $\alpha$ and the potential values for $m_{n+1}$. It might be that at some point there is no possible value for $m_{n+1}$. Alternately, we might manage to get a possible initial sequence $m_i$ and confine $\alpha$ to a small enough interval $((m_n-\epsilon)^{1/n},(m_n+\epsilon)^{1/n} )$ that we might (or might not) be able to identify it. I did not have great luck with $\lambda=1$ but my experiments with $\lambda=e , \epsilon=0.1$ and $\alpha \approx 10e$ all ended with no way to continue.

Answer by Aaron Meyerowitz for What is the spectrum of the Rado graph?

2013-03-18T20:18:47Z

The infinite Rado graph could be specified as having vertices numbered $0,1,2,\cdots$ where there is an edge $(m,i)$ when the $i$th bit of the binary expansion of $m$ is a $1$. One could look at the induced graph on the vertices $0,\cdots,n-1$ either for all $n$ or when $n$ is a power of $2$. As commented below, that is perhaps not the only choice. However it was an open ended question and I found that choice appealing. I had expected that things would be different right after a new power of $2$ compared to half way between two such. Below is a plot of the eigenvalues up to $n=129.$

Some random observations about these $130$ cases:

The number of distinct eigenvalues for n from $0$ to $12$ are $1,2,3,4,5,6,7,7,9,9,9,8,9$
Starting with $n=6$ There are $2k+3$ non-zero eigenvalues for $2^k \le n \lt 2^{k+1}.$ These are distinct with the exception of a double eigenvalue of$-2$ at $n=11.$
There is an eigenvalue of $0$ except for $n=1,3,4,5$. Hence, starting at $n=8$ it has multiplicity $n-2k-1$ for $k$ as above. That is; the multiplicity is $1$ at $n=8$ and then increases by $1$ when $n$ does, except that it drops by $2$ when $n$ is a power of $2.$
The only non-zero values which occur for more than one $n$ (up to $n=127$) are
- $-2$ for $n=9,10,11,12,13$,
- $+1$ for $n=1,4,10,11$ and
- $-1$ for $n=3,4$
The only integer eigenvalues not already mentioned are $+2$ for $n=35$ and$-4$ for $n=57$

What are some interesting almost equitable partitions which are not equitable?

2013-02-20T22:54:46Z

There have been questions lately about almost equitable partitions in graphs, for example this one which provides the definition.) Every equitable partition is almost equitable. The converse is true for regular graphs but not in general. Equitable partitions are useful for understanding eigenvalues of (the adjacency matrix of) certain graphs. There are many nice examples of equitable partitions coming from distance regular graphs, graphs with a non-trivial automorphism etc. I looked a bit and found papers about graphs with almost equitable partitions which were not equitable, but mainly as examples that it could happen. Hence

What are some interesting examples of graphs with almost equitable partitions which are not equitable? In particular (but not exclusively) infinite familes.

For me interesting would mean revealing some structure not obvious or just attractive in some way( vague I know).

As an experiment I considered a $5 \times 5$ grid with $25$ points of degrees $2,3$ and $4$. There are equitable partitions corresponding to orbits of the automorphism group (quarter rotation,half rotation,flip either of two ways). So all these have at least $6$ classes. The adjacency matrix has $13$ eigenvalues, some double, all in $\mathbb{Z}[\sqrt{3}]$. For the Laplacian there are $14$ eigenvalues including $4$ with multiplicity $4$, all are in $\mathbb{Z}[\sqrt{5}]$. The one only almost equitable partition I saw so far is in 3 classes, top and bottom rows,rows 2 and 4, middle row (and the column version of that.)

Maybe that was the wrong example, but what is a better one?

Answer by Aaron Meyerowitz for Does there exist a function (however complex) which given an input in the form of any problem which can be solved in a rigorous and non-random way can return the solution to that problem.

2013-03-18T14:55:51Z

Given any infinite sequence of integer pairs $(x_i,y_i)$ for $i \ge 0$ with distinct $x$ values, there is a unique sequence of polynomials $p_i(x)$ so that $p_i$ has degree no more than $i$ and $p_j(x_i)=y_i$ for all $j \ge i.$ So one might be tempted to say that the $p_i$ are converging to a function given by a sort of power series $P(x)$. It is also true that if the $y$ values are given by a polynomial $f(x)$ of degree $d$ then $p_i=f$ for all $i \ge d.$

However, $p_i$ will typically give no information about any values $y_j$ for $j \gt i$ and the $p_i$ will simply become more and more unwieldy.

In the simplest case that $x_i=i$ one will have $p_i=\sum_{j=0}^{i}c_j\binom{x}{j}$ and $$P(x)=\sum_{j=0}^{\infty}c_j\binom{x}{j}$$ where each $c_i$ is chosen to be whatever will make $P(i)$ equal to $y_i$ : $c_i=y_i-p_{i-1}(i)$

So the values $[0, 0], [1, -1], [2, 2], [3, -3], [4, 4], [5, -5], [6, 6], [7, -7], [8, 8], [9, -9],\cdots$ would yield coefficients $c_i$ starting out $0, -1, 4, -12, 32, -80, 192, -448, 1024, -2304$ Maybe you recognize those coefficients but perhaps the rule switches to something else starting with $x_{10}.$

Answer by Aaron Meyerowitz for signing a strongly regular graph

2013-03-17T18:59:13Z

Here are a few ideas on places to look for examples. You may not find (m)any this way.

First to eliminate a trivial case: For some people a complete graph or disjoint union of isomorphic complete graphs is a SRG. These only have two eigenvalues even without making any changes.

A SRG need not have any automorphisms but many do. This allows an easier complete search of very small cases. In a very modest search I found one legit example and a few questionable ones. Then it seems reasonable to look for ways to sign the matrix and preserve a large subgroup of the automorphism group (but I did not get anything from that.)

Essentially we are taking a graph with $e$ edges, viewing it as having $2e$ directed edges, and then giving some of them a weight of $-1$.

A 4-cycle has 4 edges or $8$ directed edges (aka $+1$ entries of the Adjacency matrix $A$)

Changing a single $1$ to $-1$ does not work.
There are $28$ ways to choose two entries, but only $6$ up to action of the Dihedral group. Changing two entries , both from the same edge, gives eigenvalues $\pm\sqrt{2}$ twice each. (That is my sole good example so enjoy it). There are also three ways to change two entries to $-1$ and get all eigenvalues $0$: the two edges leaving a vertex, the two going into a vertex, and two parallel directed edges.
there are no successful ways to change three entries.
There are $\binom84=70$ ways to choose $4$ entries to change but only $13$ up to isomorphism (maybe less but at worst I looked at some cases twice.) Four of them give all eigenvalues $0.$

Note that with two eigenvalues $\theta_1,\theta_2$ taken $k$ and $n-k$ times we need $\frac{\theta_1}{\theta2}=-\frac{n-k}{k}$ unless it is actually a single eigenvalue of $0$.

A pentagon amounts to $10$ directed edges, There is no way to change some of the entries of $A$ to $-1$ and get only two eigenvalues. There are $\binom{10}{5}=252$ ways to change $5$ of them but only $26$ up to isomorphism.
The complete bipartite graph has $18$ directed edges. Nothing works there. There would be $\binom{18}{9}=24310$ ways to change half the edges but only $681$ up to isomorphism.

I'd hoped to find an example which generalized. I did not give up after two tries but did after three. Maybe someone else will find something by looking a bit harder. Perhaps $K_{2,2,2}$ , $K_{4,4}$, or some other small case.

I also looked, without results at a few ways to weight the $2 \cdot 15=30$ directed edges from a Peterson Graph.

The obvious order $5$ rotation gives $3$ pairs of $5$ edge orbits so $64$ (or $32$ or $16$ depending how hard you wish to think) ways to sign some orbits $-1$. None worked ( assuming I programmed correctly).
Fixing a point gives orbits of sizes $3,3,6,6$ and $12$ (Probably the $12$ could be split $6,6$ but I did not try that variation. ) That does not yield anything.
I did not look at fixing a pair of vertices (setwise). This would give orbits of sizes $1,1,4,4,8,8,2?,2?.$

A similar attempt could be made for other graphs.

Answer by Aaron Meyerowitz for $\prod_{n=1}^{\infty} n{}^{\mu(n)}=\frac{1}{4 \pi ^2}$

2013-03-12T22:15:14Z

So of course it does not converge. The behavior is interesting however. Below is the graph of the $\log$ of the product going up to $5000.$ There can be runs very rich in square free integers with an even number of divisors which cause a dramatic shift. AT $509$ the product is about $5\times 10^{-13}.$ Of the next $45$ square free integers ,$15$ provide a factor around $\frac{1}{500}$ and the other $30$ provide a factor around $500$ so the product at $586$ is around $1.7 \times 10^{23}.$ Of course there are bigger swings in both directions later on. This argues against any simply minded convergence acceleration used as smoothing.

Rearranging can do anything but a reasonable procedure might be to look at the $2^k$ square free integers divisible only by (some) of the first $k$ primes. The product over those comes out to be $1$ for $p_k \ge 3.$ So this could be taken as suggesting some balance. As far as $10000$ the product never has an even denominator after $5$. However the numerator is just four times an odd number for $6590,6593$ so if forced to guess I'd guess thatit is negative someplace(s) past $10000.$ Something similar seems to be happening with larger small primes.

Answer by Aaron Meyerowitz for Does this sequence exhausts the prime numbers?

2013-03-09T22:07:16Z

You can find some amusing (I might say amazing) papers in this area by searching for "primes at a glance" and " primes at a (somewhat lengthy) glance".

In the first paper they give (along with many other interesting things) what they "believe to be a complete list" of all pairs of integers $B,L$ with

$N=B+L$
$B \ge |L|$
$\gcd(B,L)=1$
if $p \le\sqrt{N}$, then $p$ divides $BL.$
if $Q | BL$ and $p \lt q$ then $p | BL$

For $N \gt 1$ this proves $N$ to be prime as it rules out any proper divisors. Such a presentation provides an at a glance proof that $p$ is prime. For $N=31$ the presentations range from

$31=2^4+3\cdot5$

$31=2^3\cdot7\cdot11\cdot17\cdot23-3\cdot5^2\cdot13^2\cdot19$

The first primes for which they give no solutions are $541,547$

the last for which they do is

$2521=19\cdot43\cdot37\cdot2\cdot3^2\cdot5\cdot29^2\cdot41\cdot47^2-7\cdot11^3\cdot13\cdot17^2\cdot23^2\cdot31$

Without condition 5 there are many solutions. $88711$ is the product of $7,19,23,29$ and $72930$ is the product of $2,3,5,11,13,17$ so we can certainly find positive coprime integers with $1=88711x-72930y.$ Then $31=88711s-72930t$ is a difference of coprime values for $s=31x+72930$ and $t=31y+88711$ You can always do that.But probably not with $st$ having all prime factors below 31 ( in which case the prime factors would split the same way, given that none of them divide $31$.)

Answer by Aaron Meyerowitz for long enough interval of integers to solve a simultaneous congruence

2013-03-04T10:43:31Z

Note: After starting this I realized from your condition involving $\sum_i \prod_{j\ne i} a_j$ that you may have anticipated most of what I wrote, but I'll go ahead with it.

The case $K=2$ wWe will see that the problem when $k=2$ can be reduced to this: find subsets $A \subset b\mathbb{Z}$ and $B \subset a\mathbb{Z}$ with $|A|=s_1$ , $|B|=s_2$ and $\max A+B \bmod{ab}$ as small as possible. Here $a \lt b$ are coprime integers while $s_1 \lt a$ and $s_2 \lt b$ are positive integers and $X+Y=\{x+y \mid x \in X, y\in Y\}.$ Note that $A+B \mod ab$ is the set of residues $ r \bmod ab$ with $r \bmod{a} \in A$ and $r \bmod{b} \in B.$

It seems plausible, and turns out to be the case, that the minimum is frequently achieved by taking $A=\{0,b,2b,\cdots,(s_1-1)b\}$ and $B=\{0,a,2a,\cdots,(s_2-1)a\}$. If we do not reduce $\bmod ab$ then the $s_1s_2$ integers range from $0$ to $t=(s_1-1)b+(s_2-1)a$ and are separated by $s_1s_2-1$ gaps, some perhaps of size $0$ but none larger than $b-1$. In the event that $t \lt ab,$ the reduction does not change $A+B.$ and we have one final gap $\mod ab$ of length $ab-t.$ Then any interval of $ab-t+1=ab-(|B|-1)a-(|A|-1)b+1$ consecutive integers contains a member $m$ with $ m \bmod a \in A$ and $m \bmod b \in B$ (This was the problem as given.) The bound is sharp for those parameters provided that $ab-t+1 \ge b-1.$ In a sense to be made precise, this is the only example which requires an interval that long.

In any case, we always need to take at least $a+b-s_1-s_2+1$ consecutive integers to be sure to have an $m$ as above. This is because we can choose the elements which will not be in $A$ so as to exclude $ab-1,ab-2,\cdots,ab-s_1$ and then choose elements to not be in $B$ so as to also exclude $ab-s_1 \cdots ab-s_1-s_2.$ If $a+b-s_1-s_2 \le a$ then this is best possible and there are $\binom{s_1+s_2}{s_1}$ ways to do this. For slightly larger $a+b-s_1-s_2$ it may be possible to eliminate two things with some of our choices for $A$. However the optimum solutions in these cases appear to have this nature.

Larger $k:$For the generalization to larger $k$ the situation is about the same (see below if needed for the notation): Suppose $a_1 \lt a_2 \lt \cdots \lt a_k.$ Before reducing $\mod a=\prod a_i $, the integers $a_1a_2\cdots a_k(\sum_1^k\frac{i_j}{a_j})$ with $0 \le i_j \lt s_j$ range from $0$ to $t=a_1a_2\cdots a_k\sum\frac{s_j-1}{a_j}$ and have gaps of length bounded by $\prod_2^k a_i.$ Provided that $t \lt \prod a_i$, The set is unchanged by the reduction and is followed by a gap of length $(\prod a_i)-t.$ I think that this gives the longest possible gap provided that it is greater than $\prod_2^k a_i.$ This amounts to taking sets where $A_i$ consissts of $s_i$ mutiples of $\prod_{j \ne i}a_j$.

Here is visual model I find helpful. The residues $\mod 5 \cdot 17=a_1 \cdot a_2$ are in an array with the $i_1,i_2$ entry congruent to $i_j \mod a_j.$ Note that each entry is the sum of the leftmost thing in its row and top thing in its column (a multiple of $17$ and a multiple of $5$.) To move one step at a time through the integers $\mod 85$, keeping track of the residues mod $5$ and $17$, is to move at a slope of $-1$ wrapping around cyclically.

If I choose the residues $\{0,17\}=\{0,2\} \mod 5$ and $\{0,5,10\} \mod 17$ this distinguishes two rows and three columns. The intersections are the six values indicated in red, giving gaps of lengths $4,4,6,4,4,57$

$\left[ \begin {array}{ccccccccccccccccc} \color{red}{0}&35&70&20&55&\color{red}{5}&40&75&25&60& \color{red}{10}&45&80&30&65&15&50\\ 51&1&36&71&21&56&6&41&76&26& 61&11&46&81&31&66&16\\ \color{\red}{17}&52&2&37&72&\color{red}{22}&57&7&42&77& \color{\red}{ 27}&62&12&47&82&32&67\\ 68&18&53&3&38&73&23&58&8&43& 78&28&63&13&48&83&33\\ 34&69&19&54&4&39&74&24&59&9& 44&79&29&64&14&49&84\end {array} \right] $

The set of gap lengths is unchanged if the six red integers are moved together horizontally and or vertically and/or reflected vertically and/or reflected horizontally. This is the same as replacing one or both of the sets $\{0,5,10\} \mod 17$ and or $\{0,2\} \mod 5$ by an equivalent one where a set $A_i$ of residues $\mod a_i$ is equivalent to any of the sets $A_i+c$ and $-A_i+c.$ Hence we can arrange to have the longest gap end at $0$

Examples at the other extreme Suppose I still use $a,b=5,17$ but I want to have $|A|=4$ and $|B|=13.$ Then in the array I can eliminate one row and 4 columns. If I want to have the largest gap end at $0$ (since it can as easily be made to end there as anywhere else) then I need to eliminate the last few (as many as possible) of the integers $77,78,79,0,81,82,83,84.$ However a row can only eliminate two of those and a column one so best is to eliminate $79,84$ using the last row and $80,81,82,83$ using the four next to final columns. If instead I raised $|B|$ to $14$ then I would have four different ways to use one row and 3 columns to eliminate $81,82,83,84.$ So it would seem that the best option in situations such as these is use the topmost rows (assuming that rows are longer than columns), see what was eliminated by the excluded rows and then use the columns to remove the largest residues still un-eliminated. So for $|A|=3$ and $|B|=11$ we can take $A=\{0,17,51\}$ eliminating (bottom to top) $74,79,84,73,78,83$ and take $B=\{0, 5, 10, 15, 20, 35, 40, 45, 50, 55, 70\}$ with the six excluded columns just sufficient to eliminate (left to right) $75,76,77,80,81,82.$ Note that in this case, $a1,a2,s1,s2=5,17,3,11$ so $a_1a_2=85$ but $(s_1-1)a_2+(s_2-1)a_1=2\cdot 17+10\cdot 5=84.$

Notation: Suppose that $a=[a_1,a_2,\cdots,a_k]$ is a list of $k$ pairwise coprime integers and $A=[A_1,\cdots,A_k]$ is a list where $A_i$ is a set of $s_i$ residues mod $a_i.$ Where no confusion arises we will also use $a$ to denote $\prod a_i$ and $s$ to denote both the list of sizes $s=[s1,\cdots,s_k]$ as well as the integer $\prod_1^ks_j$. There are $s$ integers $\mod a$ with $x \mod a_i \in A_i$ for all $1 \le i \le k.$ This defines $s$ gaps (some perhaps of length $0$) free of any integers from this set. Let $g(a,A)=g([a_1,\cdots,a_k],[A_1,\cdots,A_k])$ be the greatest length among these gaps and $g(a,s)$ the longest such for this list $a$ among all lists of residues with $|A_i|=s_i.$

A few simple but useful observations

$g(a,A)$ is unchanged if we replace one or more sets $A_i$ by an equivalent set $A_i+c$ or $-A_i+c.$
In the case $k=1$ we have $g([a_1],[s_1])=a_1-s_1$ from taking $A_1=\{0,1,2,3,\cdots,s_1-1\}$ and this is the unique solution up to the equivalence above.
If we consider instead of consecutive integers (an arithmetic progression with common difference $1$) arithmetic progressions with a common difference $d$ (which is coprime to $\prod a_i$) then there are the same values $g(a,s)$ due to the bijection which replaces each $A_i$ by $dA_i.$

Discussion: Now that we understand the simplest case $g(a_1,s_1)=a_1-s_1$ let's consider $g(a_1,s_1,a_2,1)$ We saw from the second remark that $g(a1,s1)=g(17,3)=14$ with the unique realization (up to the equivalence of the first remark) $A_1=\{0,1,2\}$ giving gaps $0,0,14.$ What if we consider now $g(17,3,5,1)?$ Then from the first remark we see that we may assume $A_2=\{0\}$ so that we will have some three red integers in the first row (row $0$) of the array above. As we move diagonally through the array we can imagine that we are actually staying on the first row and taking jumps of length $5$ Hence from the third remark the extreme case (up to equivalence) is $\{0,5,10\}$ with gaps $5\cdot 0+4,5 \cdot 0+4,5 \cdot 14+4=4,4,74.$ It does not seem that it would be hard to explain this more carefully to account for the general case of adding a new modulus $a_{k+1}$ with $s_{k+1}=1.$

To quickly repeat some comments above: In the case $k=2$ is fairly easy to handle all at once. We can shift so that the longest gap ends at $0$ which means that we select $0$ and $s_1-1$ other entries from row $0$ along with $s_2-1$ other entries from column $0$ so we have a set of $s_1$ multiples of $a_2$ in column $0$ along with $s_2$ multiples of $a_1$ in row $0$ and all $s_1s_2$ pairwise sums. If $(s_1-1)b+(s_2-1)a$ is reasonably less than $ab$ then we should just take the rows and columns with the smallest values on the left and top. In cases as the above with $(s_1-1)a_2+(s_2-1)a_1$ greater than, or only slightly less than $ab-1$ it is better to rule out using rows and columns so as to exclude the largest entries.

Experimental results: With the consideration of equivalence classes from the first remark it is possible to check small cases, For $k=2$ and $s_1=s_2=3$ the unique extreme example is the one I described except for $a_1=4,a_2=5$ when their are two solutions giving a maximal gap of $3$ and $a_1=4,a_2=7$ with a maximal gap of $6.$ For $s_1=s_2=4$ the largest exceptions are $a_1,a_2=5,14$ and $6,7.$ These seem to resemble the "other extreme" example above. I did not see any other behavior but I did not go past $\max{(s_1,s_2)}=5.$

Geometry: The picture of a sloped trajectory in a sort of discrete plane with two parallel classes of lines of lengths $a_1$ and $a_2$ generalizes in an easy way to boxes for $k=3.$ A more formal view might be built on the cyclic group of order $a_1a_2..a_k.$ Among the many subgroups consider the $2^k$ whose order is a multiple of some (or none or all) of the $a_i.$ Then the cosets of these form a system of "subspaces" which fall into parallel classes and are closed under intersection.

Approximation: Finally, I wonder about a continuous analog: Change the model to a unit square (or cube) traversed by a line of slope $\frac{-a_2}{a_1}$ (or in the direction $(1,\frac{-a_2}{a_1},\frac{-a_3}{a_1})$) It will follow a periodic trajectory and we might wonder how long a partial trajectory could be and be bounded away (by an appropriate amount in an appropriate metric) from a set with some factored form and given size (or measure.) Although the possible details are far from clear, perhaps one consider not necessarily rational slopes and recruit results about Diophantine approximations. Perhaps the higher dimensional cases could be understood through simultaneous approximation.

Answer by Aaron Meyerowitz for Is the empty graph a tree?

2013-02-01T20:26:51Z

I think it just depends on how you want to use it. I will claim that sometimes the empty graph is best considered a tree and even a rooted tree but other times, neither. Even the one vertex tree is a little odd, it is the only tree with a degree zero vertex.

The Catalan numbers count many kinds of trees. In an Ordered Binary Tree each node may have up to two children left and/or right. If we let $C_n$ be the number of such with $n$ nodes then could exclude the empty tree and say

$C_1=1$
$C_{n+1}=C_n+C_n+\sum_{i=1}^{n-1}C_iC_{n-i}$

The first two terms for the case of only one child. But it is nicer to think of the left and right children as being themselves binary trees, both present, but perhaps one or both the empty tree.

$C_0=1$
$C_{n+1}=\sum_0^nC_iC_{n-i}$.

I think that the second approach is nicer. Particularly for the analogous situation with trinary trees.

A Full Ordered Binary Tree is as above except that a node may have either $0$ or $2$ children (thought of as nodes). There is a natural bijection between OBTs (including the empty tree) having $n$ nodes and FOBTs (not including the empty tree) having $n+1$ leaf nodes. In one direction assign each leaf node two children and in the other remove all the leaf nodes.

So here we interpret $C_n$ as the number of FOBTs with $n+1$ leaf nodes and do not bother to consider the empty tree as a FOBT.

Given a non-associative product, an expression $x_1\cdot x_2 \cdot x_k$ needs parentheses to be evaluated. We can use a FOBT with $k-1$ non-leaf nodes corresponding to the multiplications and $k$ leaves corresponding to the variables. Then $C_0$ counts the one vertex tree from the "product" $x_1.$ Now there seems no reason to count the empty tree. Of course we do like the empty product, but that is not especially relevant.

If we want to have a definition of rooted tree which does not specifically mention "the root" then we can say that a rooted tree is precisely a finite partial order $(S,\prec)$ such that

for all $u \in S$ the set $\{x \mid x \preceq u\}$ is totally ordered by $\prec$
for all $u,v \in S$ there is a common lower bound.

If we can get away with that, then the empty order is an order.

Answer by Aaron Meyerowitz for Characterizing Convex Configurations of Quadrupels of Coplanar Points via Linear (In-)equalities between Distance Sums or Differences

2013-02-24T01:03:17Z

As nicely shown above, If we merely have a set of six distances the answer is no. Rearranging that example we see that it remains no even if we are given that the points all have integer coordinates and we know the individual lengths $AB,AC,BC,AD$ but we have the two values $BC,BD$ without knowing which is which.

Given the six lengths and the full ability to do geometric constructions or algebra we can locate $D.$ Knowing $AB,AC,BC$ along with $BD$ and $CD$ limits $D$ to one of two locations which are not equally distant from $A$. Sometime the answer would be obvious such as $AD=BD=CD$ and $AB=AC=BC.$ I think that if we could go off and do calculations we could come back and know what additions and comparisons to do to answer the question. However a simple algorithm seems unlikely to me because it could depend on very minute differences.

As an easy case (again adapted from another answer): suppose we know that $AB=BC=AC$ and I next tell you " $BD=CD$ and they are both just slightly over $\frac{AC}{2}$" You might say (to yourself) " ok, the exact value doesn't matter , I just need to determine if $AD$ is more or less than $\frac{\sqrt{3}AC}{2}.$" If you are just adding, subtracting and comparing your given values then there are various rationals you can use as test cases. $6/7 \lt 84/97 \lt 1170/1351, \lt 16296/18817\lt \cdots \lt \frac{\sqrt{3}}{2}$ Also $ \frac{\sqrt{3}}{2} \lt \cdots \lt 35113/40545 \lt 2521/2911 \lt 181/209 \lt 13/15 \lt 1$ so if $97\ AD \le 84\ AC$ the point is surely inside and if $181\ AC \le 209\ AD$ it is surely outside but otherwise you don't know yet. If you go back and get the actual value of $BD=CD$ then that will tell you the accuracy you need. Say that $BD=(1/2+\epsilon)AC$ then $AD=\frac{AC\sqrt{3}}{2} \pm AC\sqrt{\epsilon+\epsilon^2}$ so an accuracy of $\epsilon AC$ will be quite sufficient. But how to translate that into a simple procedure is not that clear.

Answer by Aaron Meyerowitz for Near-linear Function aproximation

2013-02-23T13:41:44Z

I'll assume that your data is discrete.

You can pick a class of function such as $g(x)=Ax+B+C\sin(Dx+E)$ and then solve for $A,B,C,D,E$ which minimize $\sum(f(x)-g(x))^2.$

later thoughts As I think about it, that might not be that easy to solve (at least using partial derivatives, perhaps a multi-dimensional Newtons method but that does not seem worthwhile).

Any modeling is a matter of judgement. I think you would in any case first just find the best linear fit $Ax+B$ (which is easy) and then work on the values $f(x)-(Ax+B).$ Now you have the cleaner problem:

Given something which looks like random noise with mean $0$ how would you model it?

Without any further information I might just find average absolute value $V$ of the error and then add a term $(2-{\sqrt{2}})\frac{V}{2}\sin(Mx+M)$ where $M$ is a huge constant. So this is essentially random sampling from a source with mean value $0$ and mean absolute value $V$. This would be expected (I would think) to be roughly no better or worse a fit to your actual data than the line $Ax+B$ but to have the right amount of noisiness.

Answer by Aaron Meyerowitz for algorithmic almost equitable partitioning

2013-02-20T02:52:51Z

The definition to which you link says

$\forall i,j\in{1,\ldots,k}$ $\forall v, u\in V_i$ $|N(v)\cap V_j|=|N(u)\cap V_j|$, i. e. that the number of neighbors of a node $v$ in $V_i$ in the component $V_j$ does not depend on the choice of $v$.

Am I correct that that is the definition of equitable whereas almost-equitable restricts to $i \ne j$?

You might check out Partitions in matrices and graphs MR1104819

by Hughes, D. R. and Singhi, N. M. European J. Combin v 12 (1991) number 3 pages 223-235

I know it aims to be very general and as I recall, it had algorithmic aspects. But I read it a long time ago. Here is an idea which I think I might recall from that paper (but I could be totally wrong):

If you have a potential cell $C$ of a partition then you can take the corresponding characteristic vector $\mathbf{v}$ and multiply it by the Laplacian matrix once (or several times) obtaining $\mathbf{w}$. Define $i \sim j$ if $\mathbf{w}_i=\mathbf{w}_j.$ Then I think that the following is true: Any almost equitable partition having $C$ as a cell is a refinement of this partition (so the vertices of $C$ had better be equivalent under $\sim$.)

This also works if $C$ is a union of several cells (then $C$ need not be part of an equivalence class under $\sim$ so you could take each of the parts into which it was split and use them as $\mathbf{v}$). So if you are looking for fully equitable partitions ($i=j$ also required) and happen to have several degrees in the graph and then you could start with the characteristic vector of each degree class, try the procedure above to get several partitions and then restrict your attention to common refinements. I'm not sure how to adapt that to the almost equitable setting.

I'm not sure how an infinite graph would be presented and how one would check a potential partition. Perhaps the mode of presentation would give some clues.

Answer by Aaron Meyerowitz for Minimal graphs with a prescribed number of spanning trees

2013-02-18T09:08:57Z

While the theta construction (paths of lengths $a,b$ and $c$ with common endpoints) is not optimal, how bad can it be? Well the best it could be with real numbers instead of integers is $a+b+c=\sqrt{3}\sqrt{n}.$ I'd guess, based on limited evidence that using the theta construction one can always obtain $\alpha(p) \lt 2\sqrt{p}$ (say for $p \gt 1000$) In other words, $\frac{(a+b+c)^2}{p} \lt 4$

I looked at sets $\{a,b,c\}$ with members less than $101$ and pairwise co-prime (since I was aiming for primes). The only primes under $12500$ which I failed to get were $13,37,9463.$ For $n=9463$ there is $a,b,c=35,41,108$ with $\frac{(a+b+c)^2}{p} \approx 3.51.$ There are $1324$ primes $(1000 \lt p \lt 12500.)$ There are thirteen prime in this range with $\frac{(a+b+c)^2}{p} \gt 3.5.$ The other twelve are

$\small [1657, {3, 31, 46}, 3.862], [2293, {11, 23, 60}, 3.853], [4093, {11, 38, 75}, 3.757], [1093, {5, 21, 38}, 3.747],$$\small [4513, {17, 32, 81}, 3.745], [1777, {6, 31, 43}, 3.602], [1297, {6, 25, 37}, 3.565], [1153, {11, 15, 38}, 3.552],$$\small [1549, {7, 27, 40}, 3.535], [4657, {22, 31, 75}, 3.518], [7129, {24, 43, 91}, 3.502], [3457, {19, 27, 64}, 3.500]$

There are another twelve with the ratio in $(3.4,3.5).$ And $894$ of these primes (slightly more than $2/3$ ) have the ratio under $3.1.$

Comment by Aaron Meyerowitz

2013-05-22T13:45:35Z

So in fact the ( ideal) ladder hits the ground with infinite velocity! I guess that in the real world the top of the ladder slightly pulls away from the wall.

Comment by Aaron Meyerowitz

2013-05-19T21:06:48Z

For your first question you have an ordered list of $6$ unit vectors in general position (seems right to assume that). In any of the $6!$ orders the sum is zero. We can start anywhere and traverse the knot in either order so there are essentially $60$ knots. I wonder how many of them could be a trefoil. Might be an easy question. The easiest non-trivial case is $5$ unit vectors in $\mathbb{R}^2.$

Comment by Aaron Meyerowitz

2013-05-16T11:56:26Z

So for Rule 1 one seems to be getting $(2^{n-1}-1)(1+\frac{1+o(n)}{n})$.

Comment by Aaron Meyerowitz

2013-05-15T01:53:39Z

aha, you are quite right. It isn't that $a(n-1)=2^{n-1}-1$ exactly. But probably (likely not hard, but haven't checked it) for fixed $k \ge 1$ and arbitrary $n$ we have $a(k)=\frac{A(n)2^{n-1}+B(n)}{C(n)}$ where $A,B,C$ are all monic of degree $k$.

Comment by Aaron Meyerowitz

2013-05-04T03:47:06Z

Of course you are right. I corrected it.

Comment by Aaron Meyerowitz

2013-05-01T08:30:08Z

That's fairly quick... A distance regular graph, of course, need not be distance transitive. But many are. How quickly can we decide if a graph is distance transitive? It is not obvious that either bounds the other, but it would be interesting if the two differed.

Comment by Aaron Meyerowitz

2013-05-01T06:18:36Z

It is probably easier to think of it as subsets of the index set.

Comment by Aaron Meyerowitz

2013-04-29T02:24:10Z

Yes, I now realize that.

Comment by Aaron Meyerowitz

2013-04-27T21:00:00Z

In certain cases of a small disk between two larger ones you would not be able to have a plane tangent to all three spheres , but it is still an amazing proof.

Comment by Aaron Meyerowitz

2013-04-22T03:26:56Z

A proof of the form "They count the same thing in two ways" is about as good as it gets in my opinion.

Comment by Aaron Meyerowitz

2013-04-22T01:48:35Z

Easier to keep track of which classes not to bother with. Assuming that the primes $p$ are coming from a list as in Victors one line program above we could put in extra conditions before isprime of $i \mod 3 \ne 2, i \mod 5 \ne 1, i \mod 7 \ne 5, i\mod 11 \ne 3$ .

Comment by Aaron Meyerowitz

2013-04-16T20:49:28Z

@Rhett, I never invited you to join me! But if you won't go with me then where will you go? Frankly my dear....

Comment by Aaron Meyerowitz

2013-04-08T23:11:43Z

And I guess you checked the OEIS

Comment by Aaron Meyerowitz

2013-04-08T19:44:30Z

Sometimes $f+g$ takes $x$ to $f(x)+g(x)$, $fg$ takes it to $f(x)g(x)$ and $f \circ g$ takes it to $f(g(x)$ or perhaps $g(f(x)).$ If $A(S)$ is the group of bijections of the set $S$ then $\circ$ might be the preferred symbol (if any) for the group operation. The there is the left action from $A \times S$ to $S$ as well as the right action from $S \times A$ to $S.$ One wants $\circ$ to mean one thing for the first and the other for the second. One sometimes sees: "remember that GAP does it in this order but in class we do it in that order" Just be clear. It's no big deal.

Comment by Aaron Meyerowitz

2013-04-08T19:23:54Z

The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision." So YES there is something deeply interesting involving the PNT and unpredictability/irregularity, but NO the statement in the question is not that on track. I too regret that this is the wrong place to ask but encourage Bill to pursue it at math.se or elsewhere.