User ken w. smith - MathOverflow

Answer by Ken W. Smith for Topics for an Undergraduate Expository Paper in Number Theory

2012-12-28T01:57:29Z

Arithmetic functions -- there are some nice, very accessible results about arithmetic functions and some questions about these (notably the sum of divisors, $\sigma$) date back to the Greeks (perfect numbers, amicable pairs, etc.) There is also a nice algebra of arithmetic functions using the operation of convolution. Many basic number-theoretic ideas (RSA!) have arithmetic functions hiding in the background.

Example of arithmetic functions include the Euler totient $\phi$-function, $\sigma(n)=$ sum of divisors of $n$, $\tau(n)=$ number of prime divisors of $n$ and the Moebius function $\mu$.

I once had a small team of undergraduates (who had no higher mathematics in their backgrounds) create their own arithmetic functions and analyze questions about iterates of the functions.

Answer by Ken W. Smith for Is there an infinite number of combinatorial designs with $r=\lambda^{2}$

2012-12-27T14:43:01Z

I will go ahead and put this as an (attempt at an) answer. Looking at the Bruck-Ryser-Chowla theorem for symmetric designs, it appears that as long as $\lambda$ is not congruent to 2 modulo 4 then the BRC is satisfied. Therefore there are an infinite number of parameters for putative symmetric designs with $r=k=\lambda^2$. Since no family of this type appears in the chapter on symmetric designs in the CRC Handbook of Combinatorial Designs then I suppose that in general it is an open question as to whether symmetric designs with these parameters exist. (They certainly exist for $\lambda = 2, 3, 4, 5$ but are ruled out by the BRC for $\lambda = 6.$)

If a symmetric design with $r=\lambda^2$ exists then its residual design also has this property.

The problem of general $(v,b,r,k,\lambda)$ designs is much broader and I don't have an answer to the more general original question. (I assume that in the definition of ``combinatorial design" we do not allow repeated blocks.)

Answer by Ken W. Smith for Instances where an existence result precedes the constructive version

2012-08-19T20:30:24Z

As I understand it, Hilbert's original solution to Gordan's Problem was nonconstructive, proving that every algebraic variety over a field had a finite generating set. (His result is now generally cited as "Hilbert's Basis Theorem", that polynomial rings over Noetherian rings are Noetherian.)

In modern day algebraic geometry, Hilbert's nonconstructive argument is replaced by a very constructive process in which one generates a Groebner Basis for the algebraic set.

Graphs which are "distance-regular" with respect to a vertex (but not distance-regular)

2012-03-25T19:30:19Z

A distance-regular graph (DRG) is, in essence, a graph $\Gamma$ of diameter $d$ for which there are integers $c_i, a_i, b_i, (0 \le i \le d)$ such that for all vertices $x$ of $\Gamma$ and for all vertices $y$ of distance $i$ from $x$, the number of vertices $z$ adjacent to $y$ and distance $i-1$ from $x$ is $c_i$; the number of vertices $z$ adjacent to $y$ for distance $i$ from $x$ is $a_i$ and the number of $z$ adjacent to $y$ of distance $i+1$ from $x$ is $b_i.$ (See the paragraph on intersection numbers in this Wikipedia article on DRGs.)

For example, the Petersen graph is distance-regular of diameter 2. For the Petersen graph the intersection numbers are $b_0=3, b_1=2; a_1=0, a_2=2; c_1=1, c_2=1.$

Two recent research projects (one with undergraduates) have led me to some graphs that satisfy a weaker condition -- they satisfy the conditions above for some, but not all vertices $x$. These graphs are not distance regular but look distance regular with respect to a particular vertex, that is, the intersection numbers $c_i, a_i, b_i$ are well-defined for the distributions of vertices of distance $i$ from the special vertex $x.$

For example, fix a particular vertex $x_0$ in the Petersen graph and consider the six vertices not adjacent to $x_0$. These vertices lie on a hexagon, a cycle of length six. Replace that hexagon by two triangles. This new graph is no longer distance regular, but the integers $b_0, ..., c_2$ still count distributions of vertices with respect to that special vertex $x_0.$

Question. Is there a theory of these "local" distance-regular graphs? Do they have a name? (I think "locally distance-regular" is taken? There are a variety of generalizations of distance-regular graphs; a google search reveals "almost-" and "pseudo-" but none of those generalizations seem to quite describe my need for a graph which has at least one vertex $x$ with intersection numbers.)

These "local" distance-regular graphs are fairly common in the sense that one can deform almost any distance regular graph into one of these "local" distance-regular graphs in a manner similar to the way the Petersen graph was deformed, above.

I can show that some of the properties of DRGs persist in these generalizations, for example, the minimal polynomial of the DRG divides the minimal polynomial of the ``deformed" not-quite-distance-regular graph and so the eigenvalues of the DRG are a subset of the eigenvalues of the not-quite DRG. In many cases these "not-quite" DRGs have few eigenvalues.

Reconstructing graphs with vertices of degree $k$ and $k-1$

2011-12-17T16:36:24Z

The Graph Reconstruction Conjecture claims that any simple graph with 3 or more vertices is reconstructible from its "deck" of vertex-deleted subgraphs. (A nice introduction to this problem is at this Wikipedia page.)

My general question: I would be interested in any recent progress on the conjecture. The sources in the Wikipedia article seem to be quite old. (I also have a copy of a Bondy and Hemminger survey from 1977. A more recent article by Ramachandran (in pdf here) is from 2004 but like many works on this conjecture, quickly detours into other reconstruction questions, edge reconstruction, etc.)

A more specific question: since one can reconstruct the degree sequence of a graph then any regular graph can be reconstructed. But graphs with exactly two degrees, $k$ and $k-1$, seem to be quite hard to reconstruct. I would be especially interested in results related to graphs with exactly two degrees, $k$ and $k-1.$

Even more narrowly, can we reconstruct graphs in which all vertices have degree 2 or 3? (Apparently Kocay worked on that in the early 1980s, says Ramachandran.) Surely "small" graphs of degrees {2,3} are accessible to modern computers so there may now be a place for fertile exploration on this problem?

Answer by Ken W. Smith for cospectral graphs

2011-12-14T23:41:18Z

Connected strongly regular graphs with parameters $(v,k,\lambda)$ have eigenvalue $k$ appearing once and two other eigenvalues with prescribed multiplicity. In general there are many non-isomorphic graphs for a fixed parameter. There are two graphs with parameters $(16,6,2)$ and 15 with parameters $(25,12,5)$. The number of non isomorphic graphs can grow dramatically....

All strongly regular graphs with parameter $(v,k,\lambda)$ are regular (so the degree sequence is obvious) and are cospectral. Either the graph or its complement meets your bound on the number of edges.

Andries Brouwer maintains a nice webpage on strongly regular graphs here. (Check out the number of $(36,15,6)$ strongly regular graphs!)

Answer by Ken W. Smith for Counterexamples in Algebra?

2011-06-20T13:56:24Z

Desmond MacHale wrote an article, "Minimal Counterexamples in Group Theory", Mathematics Magazine, 54 (1981), no. 1, 23–28. I've found this paper useful in an introductory algebra class and I like the philosophy of the paper, "Is X true? No, probably not. So what is a smallest counterexample?" A variation on the group theory (and Irish!) tune of MacHales appears here. A followup article is "Constructing a minimal counterexample in group theory" by Arnold Feldman, also in Mathematics Magazine (1985).

Answer by Ken W. Smith for Status of the Hadamard Circulant conjecture

2011-05-11T02:43:50Z

The paper by Craigen and Jedwab points out a very definite flaw in the main theorem by Hurley, Hurley & Hurley, providing a counterexample to that theorem. So the conjecture is still open.

The paper by Leung and Schmidt (here) gives the latest information about possible counterexamples to the Circulant Hadamard conjecture.

A website of Bernhard Schmidt lists smallest open cases based (I believe) on the work of the paper cited above. The smallest open cases are, of course, quite large.

Answer by Ken W. Smith for Which mathematical ideas have done most to change history?

2011-04-13T03:21:17Z

Public key encryption is the basis for secure communication over the internet and thus the basis for our internet economy. (If my students buy a song using iTunes then they are using public key encryption. See the Wikipedia article on TSL and SSL protocols.)

A fundamental form of public key encryption (widely used now and the also the first example of public key encryption) is the RSA algorithm. It is based on Euler's theorem that $a^{\phi(n)}\equiv 1 \mod n$ for all $a$ relatively prime to $n$.

Without Euler's theorem we would not have RSA; without RSA we would not have IDEA, SSL, TSL and our internet economy.

Answer by Ken W. Smith for Names of finite groups

2010-12-06T13:47:12Z

It is difficult to come up with a consistent notation for all groups of a certain order since their construction is somewhat chaotic. We might be able to describe all the groups of order $p^3$ or $p^4$ but what about all groups of order $p^6$? Or order $p^4q^2$?

The software package GAP (http://www.gap-system.org/) has a catalogue of all groups of order up to 2000 or so and so I've sometimes referred to groups by their catalogue number, for example, SmallGroup(96, 33) refers to a particular group in that library. (As does SmallGroup(512, 1000000)!)

Comment by Ken W. Smith

2012-12-27T14:46:28Z

@Felix: thanks! -- your more general question is probably VERY open! btw, even if a symmetric design does not exist (such as $(211,36,6)$), there is still a possibility that a design exists with the residual parameters.

Comment by Ken W. Smith

2012-12-27T14:12:12Z

If we restrict the question just to symmetric designs (so that $v=b$) then there are examples $(7,4,2), (25,9,3), (61,16,4),(121,25,5)$ described in the CRC Handbook of Combinatorial Designs [link text][1] (The list does not go far enough to examine $\lambda=6$.) If one removes a block from such a design one obtains a residual design in which $r$ is still equal to $\lambda^2.$ So there are certainly a number of examples. It would be interesting to know if there are any infinite families. [1]: emba.uvm.edu/~jdinitz/hcd.html

Comment by Ken W. Smith

2012-08-25T12:44:53Z

What is the ``Markov chain matrix" $P$? Is there a connection between $P$ and the adjacency matrix of the graph $G$?

Comment by Ken W. Smith

2012-07-14T15:55:02Z

Most semigroups seem to have trivial automorphism (at least that is the result of an enumeration of small semigroups -- see the thesis of Andreas Distler, available on the internet.) A similar question (automorphism groups of free monoids vs. free groups) is at math.stackexchange.com/questions/109600. Note that semigroups and monoids obey the associativite law and yet seem to be non-symmetric in the sense that many have nontrivial automorphism groups.

Comment by Ken W. Smith

2012-03-26T14:33:27Z

A follow-up -- much of the theory I need seems to be collected in section 9.3 (Equitable Partitions) of Algebraic Graph Theory by Chris Godsil and Gordon Royle (of course!) -- which I own and is sitting on my desk! I thank you both and I apologize for not putting these ideas together....

Comment by Ken W. Smith

2012-03-26T12:38:17Z

Thanks to both of you! "Equitable partition" is the key idea I am after, I think. I'll go ahead and get the JCT(B) article through interlibrary loan.

Comment by Ken W. Smith

2011-12-18T14:01:56Z

Thanks. (The reconstruction conjecture and edge ideals, Dalili, et. al. Discrete Mathematics (Elsevier) v. 308, no. 10 (2008-01-01) p. 2002-2010. ISSN: 0012-365X.) I found a pdf by searching on the title.

Comment by Ken W. Smith

2011-12-18T13:35:07Z

Yes, I think a computer search on degrees 2 and 3 would be very useful. (What's the best way to do this? I think I have an old version of Nauty installed on my Mac but it has been a while since I used it -- sorry!) Graphs with degrees 2 & 3 would be (roughly) identified by the vertices of degree 3. "Smooth out" the vertices of degree 2, replacing edge-vertex-edge by a single edge, and one has a cubic graph. Can we reconstruct that cubic graph?

Comment by Ken W. Smith

2011-12-17T17:07:07Z

That's the survey article by Ramachandran from 2004. (I couldn't find any other relevant ones from this century.)