User gerhard paseman - MathOverflow

Answer by Gerhard Paseman for Asking about a quasicommutative semigroup

2013-02-05T19:25:54Z

The following is (for me) a bit much for a series of comments. EDIT: It is also not appropriate as an answer. The fun begins when I alternate quantifiers and turn the intended property into a semigroup identity. In an actual quasicommutative semigroup, $ab=b^3a$ would not say anything about b having torsion. Even in the finite semigroup case, there is no justification for saying that all nontrivial powers are rth powers. I leave the comedy of inferences for those who like to see how easy and wrong it can be to deduce something from a single conflation of (for all)(exists) and (exists)(for all). END EDIT. It might interest one who wants to construct an example.

The propety as described by Martin Brandenburg is a semigroup identity that implies $b^2=b^{r+1}$. Further, one finds that for $i>1$, $b^i=c^r$ for some $c$ and that $r$th powers commute with everything in the semigroup. An attempt at a reduced form for words on k letters in such a semigroup (this part needs checking before taking seriously) is something like wp where w is a squarefree word (so w does not have abcabc or similar subwords) on some subset S of the k letters and p is possibly the empty word and otherwise is an $r$th power involving only powers of the letters not in S. The subsemigroup of square or higher powers will be commutative.

If the above is correct, I see finite noncommutative examples looking like a small set of extra elements adjoined to a commutative semigroup, where the square of any extra element lies in the commutative semigroup. Not being a semigroup theorist, I sympathize with the original poster and his/her plight.

Gerhard "Ask Me About System Design" Paseman, 2013.02.05

Answer by Gerhard Paseman for Number of possible circuits with N NOR gates and M inputs

2013-02-01T03:25:24Z

Although weak upper bounds can be readily had, I would like to consider an arrangement that provides a better upper bound when more of the architecture is known. Since it helps cut down on the numbers, I will assume that the n-many gates are identical, have two inputs each, and are symmetric, so that x GATE y and y GATE x give the same results. This analysis can easily extend to gates with more inputs that are not symmetric. Knowing something of the feedback portion will be crucial to refining the estimate.

Let us start with the purely combinatorial portion. All the gates in this portion take their inputs from the m provided inputs. As an input can be repeated, there can be up to m^2 different possible basic functions represented by a 2 input gate on the m inputs. Because of symmetry and the fact that the same input line can be repeated, there are M = (m+1) choose 2 different possible outputs.

If order is important, then C such gates can be painted with the M colors in M^C different ways. However, we can get a tighter bound on the number of functionally distinct circuits by ordering the M colors and arranging the gates in color order. If I got it right, this results in CC= (M+C+1) choose (M+1) distinct circuits.

Now of the remaining number (N-C) of gates, let us assume F of them have their outputs involved in feedback mechanisms. Thus there are I=(m+C+F) many possibilities for inputs to these F many gates. Order is important here, as the F gates are interwired, so I will settle for a weak bound of FF= ((I+1) choose 2)^F possibly distinct subcircuits. There may be a way to show that enough redundancy exists that the actual number of distinct subcircuits is more like FF/(F!), but a professional graph theorist should be consulted for this part.

Finally the rest of the N gates, say R, draw from the J = (m +C +F) signals available, but since these are not combinatorial circuits, one has something like K= (J+1) choose 2 - (m+1) choose 2 possibilities, and this is just like the combinatorial case before, as we can eliminate redundancy and orient the outputs as we please, so we actually have RR= (R+K+1) choose (K+1) possibilities.

So, for a given triple (C,F,R) of nonnegative integers summing to N, there is an upper bound of CC*FF*RR circuits for that triple, with a final upper bound being a sum over all such triples of that number of circuits.

Gerhard "Ask Me About Programmable Logic" Paseman, 2013.01.31

Answer by Gerhard Paseman for sorting two paired lists of real numbers to minimize consecutive absolute differences

2013-01-23T20:34:37Z

Here is something to try. Even if it fails, knowing why it fails might be useful.

Consider the Steiner tree joining your set of points. It should have minimal length and can give you a goal. If the Steiner tree has branches at points that are not on your vertex set, consider a tour that does one subtree followed by the other subtree followed by the last subtree in decreasing order of branch length.

Now that I think on it, there is potential for enough triple branch points that you might be able to reduce something like exact three cover to this problem. Locally, though, you might consider Steiner tree suggestions as to order. If not Steiner tree, then whatever tree is suggested by the Manhattan metric.

EDIT: indeed, months in the laboratory can save hours spent in the library. As Gerry Myerson suggests in his comment, there are computationally infeasible problems related to Steiner trees, and I have likely suggested one above. Moreover, the problem of rectilinear Steiner trees has been studied, thus giving more search terms for the original poster to use. Even so, there are good approximations to some Steiner tree problems, and I suspect this problem will be similar. END EDIT.

Gerhard "As Lovely As A Tree" Paseman, 2013.01.23

Answer by Gerhard Paseman for Maximum distance within a subset of permutations

2013-01-17T21:06:33Z

Even for q=2 it is a nice problem. In this case it is easy to show that an element of P is a concatenation of cycles like (2 ... m 1), which has inversion count (m-1). The maximal inversion count for an element of P is then (n-1), and for an element of the form xy^-1 I believe it can lie outside of P and have inversion count 2n-3.

I don't know what it will be for general q, but since each element can move at most q-1 elements forward, I suspect an upper bound like qn will apply for elements of the form xy^-1, and that P will be closed under such terms only when q=n.

I don't know any references. Any that are found I hope will be posted here.

Gerhard "Also Interested In Inversion Density" Paseman, 2013.01.17

Answer by Gerhard Paseman for Hamiltonian cycles in power-graphs

2013-01-17T13:34:33Z

This is meant to address the comments in response to my comment. It also contains some "shoot from the lip" analysis, so may help in forming an answer, even if I get some of it wrong. It is not an answer however. I am focusing purely on the case k=2 so that the sum of the indices is a square implies an edge between the corresponding vertices.

The degree of vertex j is roughly sqrt(m+j) - sqrt(j), where m is the number of vertices. Adding vertices 33 and 34 adds two vertices of degree 3 to a graph that is (by assertion in the original post) Hamiltonian, so I envision a big cycle of 32 vertices with two additional degree 3 vertices hanging from it. Further, the vertices are attached at vertices in the big cycle which are "neighboring" in the canonical ordering; if enough of these points of attachment are neighboring in the cycle as well, then a larger cycle can be made from the existing cycle by removing two edges from the big cycle and grafting on the two vertices in a fashion I won't describe here but is easily pictured by people experienced with this kind of problem.

For small m, one can't guarantee that the two pairs of edges always exist, but as m grows, one may be able to give a guarantee of such a graft of two vertices: find integers a and b less than m such that m+a+1 and m+b+1 are squares and 2a-1 and 2b-1 are also squares, and then one can graft m+1 and m+2 on to the cycle for m vertices.

Gerhard "Circling The Squares? Not Impossible" Paseman, 2013.01.17

Answer by Gerhard Paseman for What is the maximal sparsity of a matrix?

2013-01-15T18:08:22Z

I expect not. If I get your question, you are asking for a basis for R, the row space of G, that has as many zero coordinates as possible. I can imagine that there are subspaces of dimension m inside F^2m for m small with respect to the cardinality of the base field F that avoid bases with more than the minimal number, but I cannot at this time provide explicit examples with proof for all n. Something that should work is having the ith row of G be e_i concatenated with f_i, where e_i is the canonical ith basis vector with m-1 zeros and one 1, and f_i is an m vector of values of (x^(i-1) +i) evaluated at x=1 to m, but I have only looked at the case m=2, where the rows are 1 0 2 2 and 0 1 3 4. The argument should go something like : if I produce k zeroes in "the second half" of such a G, I take away k or more zeros in "the first half" because the coefficients of the polynomial which is generated in the second half will dictate many nonzero entries in the first half, but I have not done the whole argument myself.

Gerhard "Ask Me About System Design" Paseman, 2013.01.15

Answer by Gerhard Paseman for power of adjacency matrix

2013-01-04T03:02:40Z

Let us take the graph G to be $K_2$. Your proposed H would have to be a zero matrix for all powers of H greater than 1. However, H would have to be nonnilpotent to record the paths of length 1. The upshot is that the path enumeration does not correspond to matrix multiplication. I would be surprised if any graphs G had an H that would work as you specify even for values of l at most 3.

Gerhard "Ask Me About System Design" Paseman, 2013.01.03

Answer by Gerhard Paseman for Math for a cake

2012-12-29T19:45:28Z

I think the diagram should be several dotted rays emanating from the same point, arranged so that if you cut along the lines, each piece will have the same volume of cake and of frosting. It is an impressive diagram when the number of pieces is a not too small odd number such as 5, 7, or 9.

(There is also an interactive n player version.)

Gerhard "Save A Piece For Me" Paseman, 2012.12.29

Answer by Gerhard Paseman for Smallest square to wrap a cylinder

2012-12-25T23:46:59Z

Perhaps Joseph can fill in this description with a picture.

In square with vertices A, B, C, and D in clockwise order, draw a line from A to a point P on BC. If the length of AP is longer than the circumference R of the inscribed circle of ABP, then a cylinder with circumference R and height which I leave you to determine can be wrapped by ABCD.

_{(Image added by J.O'Rourke)}

Gerhard "Wishing You A Happy New Year" Paseman, 2012.12.25

Answer by Gerhard Paseman for Similarity measure between 2 bi-partite graph.

2012-12-20T18:10:52Z

You might try tackling the problem from the other end in more detail: given a (large) set S of relational structures, what functions from SxS to the real interval [0,1] will serve as similarity measures?

If you can place a partial order on S and ask that the measure preserve some aspects of that order, that will limit the class of functions quite a bit. If there is a natural topology on S, you may want f to be invariant under certain induced homeomorphisms of S x S . If you want to conclude some algebraic relations from two nearly similar structures, you might try modding out S by those algebraic relations (or understand why you can't) and see how f should vary (or not vary) across each equivalence class.

These are detailed ways of asking "what do you want to measure really?" and "what are you going to do with (ask of) the measure when you get it?" .

Gerhard "Ask Me About System Design" Paseman, 2012.12.20

Answer by Gerhard Paseman for Excellent mathematical explanations

2012-12-19T04:24:46Z

I think explanatory is a group concept: a proof is explanatory when it affects a group of readers in such a way that they can explain the proof to others after they read it. There may be a more philosophical way to say it, but leaving the concept to an individual is a practical mistake in my opinion.

As an example, I proffer the compactness theorem for first order logic: a set of sentences has a model if and only if every finite subset of that set has a model. One can check several sources to get the full meaning and impact of the theorem and underlying concepts, and then go through several technical details in many of the proofs, but I will offer an explanatory hint: proofs are finite. This is used as a mnemonic for the challenging part: if the set does not have a model, there is a (finite) proof of contradiction, which suggests the appropriate finite subset to choose as not having a model. I invite the mathematical logic part of the MathOverflow community to enhance this into an explanatory proof example.

Gerhard "Doing The Writeup Costs More" Paseman, 2012.12.18

Answer by Gerhard Paseman for Positive results coming from paradoxes

2012-12-15T18:31:20Z

More in the spirit than the letter of the question, some of Alan Turing's work can be seen as applications of contradiction. The development of the Turing Machine and using it to resolve Hilbert's Entscheidungsproblem can be seen as a successful use of the Liar Paradox, and elsewhere I read a quote which suggested that Turing took a result from mathematical logic (from a contradiction one can prove anything) and used it to help build one of the codebreaking systems used in World War II.

Gerhard "Ask Me About Me Unasking" Paseman, 2012.12.15

Answer by Gerhard Paseman for How should one look at the set of compatible ring structures on a given group?

2012-12-12T20:23:52Z

I think the answer depends on what you want to accomplish.

At this writing, two other answers have given a (primarily in my opinion) point of view from a mathematical logic perspective. Let me suggest a general algebraic or computer science perspective, but also note that with some imagination one could find some useful applications from a perspective based in dynamical systems or statistics or number theory or combinatorics.

I may need to design an information representation system which will help with data storage or transmission. In fact, I may need several such representations which have certain algebraic relationships. Assuming I have the group G as a required form of addition, I might view the possible extensions as a family of clones on the set which are generated by the addition and one of the choices for multiplication. I may find that several of the choices give the same term functions or operations, in which case it may be useful to mod out by an appropriate equivalence to organize the analysis. If you ask, I can spin out some other requirements with algebraic consequences for this generalized scenario.

Gerhard "Which Hammers Will You Use?" Paseman, 2012.12.12

Answer by Gerhard Paseman for Sieve of Erathostenes: removing consecutive items

2012-12-08T23:07:16Z

Now that it looks like I am close to the intent of the question, I will point in the direction of the answer.

I recommend checking out wheel sieving using an array of differences. Note that if you store differences between unmarked items, you save on space and add a little on time: to get the next candidate add the current difference to the current candidate. However, the sequence of differences is periodic, so you can save a lot of space and manage time more effectively by just doing the work needed in one period. Thus, instead of looking at

2 2 2 2 2 ...

4 2 4 2 4 2 ...

6 4 2 4 2 4 6 2 6 4 ...

you instead work with 2 then with 4 2 then with 6 4 2 4 2 4 6 2 and so on. I invite you to find the algorithm on your own. Crandall and Pomerance have an algorithmic prime number book which has pseudocode if you want a reference.

The relevance of the above is that you are looking for an array of differences where the first difference is q-1 and one of the differences is 2q. I am confident there is one where q is less than 97. Possibly q is 43. When you find it, you will have (be able to construct) an example as suggested above, and where the code you mentioned will fail to remove a composite number.

Gerhard "Yes, Jacobsthal's Function Is Related" Paseman, 2012.12.08

Answer by Gerhard Paseman for Nonzero convex combinations of convex hull vertices to yield an inner point

2012-11-25T20:51:17Z

The following is not a proof (you'll see why in a moment), but is the basis for my belief that there are points which are interior to the convex hull and are nontrivial linear combinations of all the vertices of the convex hull.

Take V, the set all vertices of the convex hull in d dimensions, and do your best to partition into neighboring sets of size d+1. For a simplex in d dimensions, some version of barycentric coordinates should make it clear that each neighboring set has a realm of points interior to the hull which contains a simplex worth of points that are nontrivial combinations of each set. The effect of the partition is to replace the problem of size V with one of size roughly V/d: pick one point which is a representative combination of each neighboring set, and form V', while reusing any vertices from V that were left out of the initial partition. You should be able to work your way down to at most 2d interior vertices, and you might even arrange the result to be convex at each step.

This is not a proof because I am not guaranteeing convexity, nor that when you get down to at most 2d vertices that things will work out. In my geometric worldview however, I can imagine lopping off d vertices at a time in a controlled fashion to converge to a particular interior point, so the picture above might be useful in showing which (if not all) interior points are nontrivial combinations of all the vertices.

Gerhard "One Simplex At A Time" Paseman, 2012.11.25

Answer by Gerhard Paseman for Measuring big stuff

2012-11-22T18:42:21Z

One can construct a framework to analyze these questions, but not without giving up something.

Almost all finite algebras (of finite similarity type, on a labeled set, and other technicalities which apply) generate finitely based varieties in universal algebra. This is justified by looking at multiplication tables on an underlying set of n elements, choosing a subset of them that satisfy a certain property, computing a ratio R(n), and then showing that this ratio goes to 1 as n grows. Note that it is no longer looking at "all" finite algebras, but at representatives of such, and the ratio R(n) may have a limit which may bear no relation to an analogous quantity defined for countably infinite algebras: R() might not be continuously extended to all cardinals or even enough ordinals.

One can try a similar framework for arbitrary cardinalities, using the appropriate notions of measure as suggested in Joel Hamkins's post. Let me suggest an alternative idea which may make sense. Consider a set sized collection of structures, as well as the associated theory describing a class containing that set. Ideally the collection can be embedded in a large model of the same theory, and one can now ask if there are models that exist in which the set is embedded and the ratio R of some subset is as large or as small as possible, relative to a measure on the large model and using certain minimality considerations to avoid trivial and uninteresting consequences.

If you are still interested in looking at "all" structures, you will still need a container to hold them. I do not know about functors from the "power category" of a category to the reals, but if I were to attempt measuring inside a category, that is where I would start.

Gerhard "Ask Me About System Design" Paseman, 2012.11.22

Answer by Gerhard Paseman for Can pure mathematics harness citizen science?

2012-11-18T19:56:52Z

One might find an analogy useful. Can one harness citizen volunteerism in building a bridge?

Indeed, many might find a bridge more useful, and any experience in bridge building, materials acquisition, aesthetic design, or even fund raising can be used. However, to do a good job, the primary work should be the domain of those trained in the discipline of bridge-building. Even the advice of experienced but retired bridgebuilders should not be taken verbatim, but should always be considered and possibly dismissed against the situation of the present bridge being built.

Mathematics is not bridge building, but if the goal is to involve citizens (and not just their computers), then for a project to be successful, it must not try to get citizens to do things for which they are inadequately trained. There are many ways to run a computer program the wrong way; I would trust the masses to find a number of bugs in a program, but not to verify its correctness. So the citizens could participate in testing certain grapsable aspects of a theory, assuming there are parts that can be made accessible.

I would also turn to the masses for inspiration and for pedagogical testing. If I give a lecture to a group of people, I am interested in the feedback of those who did not understand it, or those who had a different perspective. I would appreciate any helpful (to me) efforts made to improve or broaden the scope of my communication, be it written or otherwise. I would also appreciate reasonable attempts at communicating a different perspective of the issue, so that I could "steal the idea" and use it elsewhere.

I have more than once had the fantasy of making an adventure-based computer game where the goal and steps to arrive it could be mapped either to a soution to an optimization problem or proof attempts at some interesting conjecture. Software design systems have evolved to the point where the fantasy is being realized, if only in early stages. That would be another avenue for non-trained participants to contribute.

Gerhard "Ask Me About System Design" Paseman, 2012.11.18

Answer by Gerhard Paseman for max # of words with restricted total content

2012-11-16T20:59:54Z

If you know L is small and M/L is large compared to the number of symbols available, you might start with crude estimates such as $A^L$ words requiring $LA^{(L-1)}$ symbols of each kind from an alphabet of size A. If A=2 you can use partial sums $\sum \binom{L}{i}$ to guess how many words you get using a sea of b's and $\sum i\binom{L}{i}$ many a's. Of course it gets more complex with more letters, but you could use the above result as a sort of multiplier. For exact estimates for every case, that is likely to be NP, possibly NP complete.

Gerhard "Ask Me About System Design" Paseman, 2012.11.16

Answer by Gerhard Paseman for Does every bipartite graph with 512 edges have an induced subgraph with 256 edges?

2012-11-14T22:13:20Z

Even though this is not a complete answer, there are enough elements in this posting that I think someone can use to show domotorp where not to look for a counterexample. I also want to separate it from the marginally useful clutter in the other post of mine. Recall that I am focused on showing every bipartite graph H with exactly 512 edges has a subset of vertices which yields G, our target of an induced subgraph of H with exactly 256 edges.

A useful fact: if n is a prime power, if M is a multiset of positive proper divisors of n with sum equal to n, then there is a submultiset M' of M with sum kn/p, where k and p are positive integers, k is less than p, and p is the prime dividing n. A corollary of this fact is that any positive number of independent vertices whose degree sum is at least 256 and whose neighbors have degrees which are precisely powers of 2 will have an induced subgraph G on precisely that set of independent vertices. Edit: so that the corollary reads correctly, assume a subgraph H of K_a,b with degree sum of the a vertices at least 256 and the degrees of the b vertices are appropriate powers of 2. Then G subgraph of K_a,b' exists as an induced subgraph of H. End Edit.

From the corollary we get that domotorp won't find any counterexample graphs H which are subgraphs of K_a,b for a=1 or a=2. Further, for a=3 or 4, there won't be any counterexamples because at least two of the independent vertices of H will have degree sum at least 256. However, I want to refine the case of a=4 a bit.

Let J be a subgraph of K_4,b with number of edges n = 256 + 3k for some nonegative integer k. Then J also has an induced subgraph G: remove the b vertices of degree 3 and whatever else is needed to achieve the target number of edges. If J has a wealth of degrees, remove vertices of degrees 1,2, or 4 until n=256+3k as above. Otherwise J has less than 264 edges or else the b vertices all have degree 3, with at most one exception which must be of degree 2. Now from the four independent vertices, remove from J that vertex which has smallest degree. The result will either have less than 260 edges, or will have a b vertex of degree 1 or at least two of degree 2, or a single edge will be removed leaving a K_3,b subgraph. In the first case J had less than 350 edges, the second and third cases will yield the goal graph G, and the final case will yield no G unless b is at least 128. The upshot is that if J has more than 381 edges, it will have a target graph G as an induced subgraph.

I worried the case a=4 to bits for a couple of reasons: one is to establish that any H which is a subgraph of K_5,b will have four of the five independent vertices with degree sum more than 400 (and thus will not be a counterexample), and two is to put a Rube Goldbergian type cap on this post for a=6. This proof idea is neat, and might be extendible, but I am going to give others the chance to do it.

Let H be a subgraph with 512 edges and be a subgraph of K_6,b. Note that if any two of the six independent vertices have degree sum at least 256 or any of those six has degree less than 12, I can turn to cases for a=2 and a=5 and assert that a target G exists.

I will now find four of the six vertices and hope that there is a G that uses those vertices. Note that we may assume the four vertices have degree sum at least 256.

First consider the degree sums of the six mod 3. The sum of the sums is 2=512 mod 3. Suppose two of the degrees mod 3 are 2. Then the remaining four have degree sum equal mod 3 to 256, so I can use that to produce G. So assume at most one of the six degrees is 2 mod 3. Then if there is one other nonzero degree mod 3, there is at least one which is zero mod 3, and those two I exclude from the four to get another degree sum equal mod 3 to 256, and again I get G. The remaining case that resolves nicely is if none are 2 mod 3, and again I can find G.

The last case is that one of the six vertices has degree 2 mod 3, and all the rest are 0 mod 3. Of the remaining 5, I can try to choose some subset of 4 and hope for that subgraph to not fall in the case where the multiset of b vertices foils me by having all threes or all threes and one two. But if I am so unlucky, then I take all 5 vertices to get a degree set with some fours or some ones, as well as some threes or twos (remember at least 12 degrees will be incremented, although some of them might have started at 0). So I can guarantee a multiset of degrees that allow the composition I want, and gain my prize graph G.

The things I do for bounty!

Gerhard "Wait Till You See Seven" Paseman, 2012.11.14

Answer by Gerhard Paseman for Does every bipartite graph with 512 edges have an induced subgraph with 256 edges?

2012-11-09T07:21:22Z

Domotorp and ARupinski likely know this already, but I thought I would record this as an initial foray into cornering a counterexample by a process of elimination. I will not bother with the general case, but focus on the specification of 256 out of 512. Let G be the collection of all bipartite graphs with 256 edges.

I will consider bipartite graphs only, and my concern is with the size of the smaller vertex set and how many edges can come from it. Certainly any node with degree at least 256 will contain an induced subgraph from G. Further any two nodes in the small set with combined degree of 256 or greater will also contain a subgraph from G. There is likely a better characterization than the following: any three vertices with combined degree of 383 and any 4 vertices with combined degree of 510 will produce a subgraph from G. (Note I am focusing on small independent vertex sets.)

Of course we can ignore vertices of degree 0. If we can characterize nicely the graphs with, say, an independent set of 3 vertices and a large number of edges (but fewer than 383) which do not have a subgraph from G, we might be able to use this to classify such graphs with larger independent sets, working our way up to 23 vertices, the rough square root of 512.

EDIT 2012.11.11 Unfortunately the analysis below is not quite right. One can find a subgraph of $K_{4,96}$ with $3*96=288$ edges which contains no induced subgraph from G. It turns out that if there are enough edges and the degrees of the larger set are anything but a multiset of 3's with at most one 2, then the conclusion holds and indeed $267$ edges are enough. I am confident that this line of investigation will produce something useful, but the treatment below is not enough. In particular, I am now unsure there is no counterexample which is not a subgraph of, say, $K_{7,n}$ for some $n$. END EDIT 2012.11.11

EDIT 2012.11.09 This problem is not exactly one about submultisets of integers and number theory, but taking that slant cuts a wide swath in the forest of bipartite graphs on 512 edges.

The major reason for needing 382 edges coming from 3 independent points while requiring less than 270 points coming from 4 independent points can be viewed as purely number-theoretic: given a=3 and b=127, there are no integers c and d such that $0 \leq c \leq a$ and $0 \leq d \leq b$ and $cd=256$. So $K_{3,127}$ is a graph of 381 edges which has no induced subgraph belonging to G. However, number theory can be used to show 382 edges from 3 points suffice, as we can either remove one of the three points and work with the remaining 2, or we look at the one point with degree 128 and note it has enough neighbors of the right degree that we just need to remove neighbors of degree 3 (or smaller degree if we run out) to achieve an induced subgraph from G.

That 4 points requires a lot fewer edges results from just needing enough residue classes mod 4 to take care of any problems: either there is a $K_{4,64}$ subgraph hidden, or there are at least enough vertices of degree 1,2, and 3 to adjust the sum mod 4. As a result, it is clear that $252+ 4*3$ is enough edges to find a subgraph from G, so let's be generous and say a combined degree of 280 suffices for 4 vertices.

We can now leverage that estimate and say that for 5 (and 6 and 7) vertices that 350 (and 420 and 490) edges respectively between them are enough to find a subgraph from G, either by removing neighbors of the 5 vertices, or by removing the vertex among the five with smallest degree, reducing it to a previous case.

Since 8 divides 256, we need either find a subgraph of the form $K_{8,32}$ or enough vertices of smaller degrees to finish the job. Rough estimates give 304 as a sufficient combined degree, which we can now leverage to say that no counterexamples on 512 edges from 13 vertices will be found.

Likely we can extend it by analyzing the case of 12 vertices further, but I will save that for later. I now suspect that domotorp will not get his counterexample for bipartite graphs with $2^n$ edges for $n \lt 10$. END EDIT 2012.11.09

Gerhard "Inching His Way Toward Bounty" Paseman, 2012.11.08

Answer by Gerhard Paseman for What is the number of $2n\times 2n$-matrices $g=\begin{pmatrix} A & B \\\ C & -A^{t} \end{pmatrix}$, $B$ and $C$ symmetric, over the finite field $\mathbb{F}\_{q}$ with $\mathrm{rank}(g)=k$?

2012-11-07T18:00:39Z

Just for the (virtual) glory of possible reputation points, here is the comment as an answer.

The columns can be switched to put B and C on the main diagonal, and multiplication of the bottom rows by -1 should produce a symmetric matrix from one of the desired form. This should be a bijective rank preserving operation which takes the current problem to one of counting symmetric matrices of a given rank over the chosen field. I am guessing that this new version is handled in the literature.

Gerhard "Ask Me About System Design" Paseman, 2012.11.07

Answer by Gerhard Paseman for Believing the Conjectures

2012-10-25T16:32:02Z

Rather than give an example with characterization, I will give an example and invite characterization.

Harry Altman gives a nice description of $c(n)$, what I call the one-complexity of an integer $n$, at this accepted answer of MathOverflow question 75698.

Using $\lg$ to mean $\log$ to the base $3$, it is clear that for $n>1$, one has $5 \lg(n) > c(n) \ge 3 \lg(n)$. I conjecture that $5$ can be replaced by $4$. Is this a negative instance of maximize?

Gerhard "Enquiring Minds Want To Know" Paseman, 2012.10.25

Answer by Gerhard Paseman for Large Intersecting Subsets of a Set

2012-10-24T05:04:23Z

Likely a lower bound is below $2n$. There are many even $n$ for which a real Hadamard matrix of order $2n$, which when normalized to have a row of all 1's yields $2n-1$ rows (and thus that many sets of $n$ elements), each two of which share exactly $n/2$ columns with values of $-1$. Possibly conference matrices could work for odd $n$, and if only $n$ rows are required, then a lower bound of less than $2n-1$ is possible for many even $n$.

Gerhard "Ask Me About Binary Matrices" Paseman, 2012.10.23

Answer by Gerhard Paseman for analogue of a set with n binary operations

2012-10-23T17:32:42Z

I've decided to expand my comment since I like my interpretation of your idea of independence.

Let's use the language of universal algebra, where we take a well understood case of an underlying set A and some system F of total functions f of finite arity n (so $f:A^n\longrightarrow A)$. For increased graspibility, I will assume A is a finite set and F is a finite nonempty tuple, where in the question all the functions in F have $n=2$, but I will allow $n$ the freedom to vary.

One reading of the poster's notion of independence is related to indecomposability of F: given A,F (I am omitting the brackets of the traditional notation), it should not be able to represent it in a nontrivial fashion as some amalgam of A,G and A,H, where G and H are smaller tuples. (I will pretend that the mechanism of tuple concatenation is not allowed, e.g. F = G concat H is illegal.) In particular, each f in F is not derivable from the other operations in F. Using 1 in A as a symbol for a constant function, which I will also call a function of arity 0, the algebras A,+,%,1 and A,+,%,1,g are different, but if g is essentially the function derived from the term (x%(x+1)), then the second algebra does not meet the notion of independence.

A fuller exposition of this notion can be seen in looking at certain closed collections of functions on A, called clones. At http://en.wikipedia.org/wiki/Post's_lattice one can see containment relations as well as lists of generators for each clone. Most of the generators are binary functions, but some functions of higher arity are needed since there are infinitely many classes of such functions. By itself, each generating tuple F is a tuple for such an independent algebra {0,1},F .

Now for larger sets, there are larger examples, including the n-quasigroup examples suggested by Aaron Meyerowitz. It is not clear to me that such examples are independent in the above sense, however. There are also n-semilattices as well as lattices enriched with n extra binary operations; I will let you search the general algebra literature for those.

There are also primal algebras, which have F as a one-tuple on a finite set A, such that the single (usually binary) function f in F can generate all other functions on A. Also there are quasiprimal algebras which are like primal algebras, except their clones are maximal but incomplete: adding any other function outside their clone to the signature F would generate the clone of all functions.

This may read more like an advertisement for clone theory than an answer, but the post did ask for other points of view.

Gerhard "Ask Me About System Design" Paseman, 2012.10.23

Answer by Gerhard Paseman for Analogues of Jacobsthal's function

2012-10-22T21:43:08Z

In looking for some simple bounds on Jacobsthal's function, I came across an argument which can be viewed as a slight modification of an argument of Kanold in his 1967 paper in Math. Annalen 170. (It could be viewed as a recombination of Hilfsatz 4 and Saetze 2,3, and 4.) However, Kanold's wording does not reflect the perspective above offered by Timothy Foo, and I want to suggest a technique that he might apply to his analogues.

Kanold shows an upper bound on $g(nm)$ with $n$ coprime to $m$ as the smaller of two expressions, one slightly smaller than $ng(m)$ and the other slightly smaller than $mg(n)$. A key fact is that the coprimality with respect to $n$ of members of an arithmetic progression AP with difference $m$ are not severely altered by multiplication mod $n$ by $f$, the inverse of $m$. Now AP$f$ looks mod $n$ like a sequence of common difference 1, so any $g(n)$ consecutive members of AP$f$ (and thus of AP) will have a member coprime to $n$.

The perspective here is that there is a map which preserves both coprimality status and enough order to get results mod $n$. What brings it home is if we use Timothy's perspective, we take an integer $N=nm$ and view it as a Cartesian product, then we can use a kind of (limited order, limited coprimality)-preserving transformation to get results like those of Jacobshal and Kanold. At present they will not be as good as Iwaniec's techniques, but for the original problem I am finding results which improve on those of Kanold, and I suspect Timothy can use them for his analogues, once he finds the right maps.

For those who might prefer a revised take on Kanold's Hilfsatz 4, here is the key idea: for squarefree $n$ and nice divisor $d$ of $n$, let's write $f=n/d$, note that $f$ and $d$ are coprime, and finally that any $g(d)$ consecutive members of the sequence $1+tf$ as $t$ ranges over the integers have at least one member coprime to $d$ as well as coprime to $f$. This immediately leads to $g(n)\leq fg(d)$.

I will follow up elsewhere with how nicely this can be used, as wells as remarks on a recent arXiv preprint which helped inspire this post.

Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2012.10.22

Answer by Gerhard Paseman for How many binary operations are associative?

2012-10-22T00:22:00Z

Here is a guide to the intuition. I will not swear that the numerics are exact, but I will bet that the numerical truth is not far off.

Look at the diagonal for the multiplication table of a (labeled) groupoid on $n>3$ elements. Of the n^n possibilities, only one of them is idempotent, so with one exception aa=b will happen for some a and some b different from a. Now all we need for associativity to fail in this case is that ab and ba are different, which will happen for all but n of the n^2 possibilities. So we are already looking at associativity happening only on a small fraction of all (non-idempotent) tables, especially as there are often several candidates for a, and only one is needed.

Even for idempotent groupoids, one finds a,b,c distinct and needs to consider only d=ab, g=bc, and the ways in which dc and ag can fail to be equal. Again in rough terms we are talking about n^(-2), and this is just by fixing a,b, and c in advance, and that for the 1 out of n^n tables that are idempotent.

I'll let someone else tighten up the numerics. For strengthening Joseph's intuition, I hope this will suffice.

Gerhard "Ask Me About 2-Deficient Groupoids" Paseman, 2012.10.21

Answer by Gerhard Paseman for Provided a list of sets, $L$, computing an array where each entry $q_i \in Q$ is the family of sets in $L$ that have intersection $k$ with $l_i \in L$

2012-10-21T07:02:32Z

Probably the optimization that you want to take is the following: if j > i and j is in q_i, then i is going to be in q_j. Here I assume the q_i are sets of indices, and that j is in q_i precisely when l_i intersect l_j has size exactly k.

Beyond that, I see no optimization one can take in the general case, given that k is fixed in advance. There may be some special cases, for example when l_i has less than k elements, you can skip processing of it. Also, if there is a special order, say you know some l's are subsets of others, then you can do some speedup.

In general though, things won't be much faster than, for all i and j with i < j, computing l_i intersect l_j and determining if that intersection has the right size.

Now if the goal is to find a value of k such that q_i cap q_{i+1} is nonempty for all i, that may take a little longer, but there won't be that many distinct values of k to check.

Gerhard "Ask Me About System Design" Paseman, 2012.10.21

Answer by Gerhard Paseman for Real functions with finitely many zeroes

2012-10-16T17:00:52Z

Here is a general algebraic approach which may give you some help.
It may even solve your problem, although I am not promising that.

Clones in universal algebra are sets of functions which are closed under having projections of all arities and functional composition. Although I was not trained to do this, they can be viewed as a graded collection by arity, and one can look at the binary or ternary or (as in your case) unary members of the clone.

A simple result is that if one has a clone generated by a beginning set of functions B, then all the functions of each grade can be determined by B acting on a sufficiently large subset of members of just that grade, without using members of the other grades.

Something that you would like to have happen is to find a clone whose unary grade a) contains only functions with finitely many zeros b) is generated by operations in a small set B which are precisely those used in your target function (which I will call g instead of f''), and c) contains g.

Much as you might like it, that may not happen because B is "too rich" to be able to satisfy condition a). One approach to try is to "thin out" B: create some terms out of functions of B, make a new set B', and hope to make a subclone which will satisfy a). Hopefully you will be able to satisfy c), but thinning out the generating set may also toss out g .

Alternatively, you could look at the (unary grade of the) clone generated by g, or by g and a skilled choice of operations from B. If g's clone already contains functions with infinitely many zeros, then so will any clone that contains g, in which case you will know that a purely clone theoretic approach, even with a judicious choice from B, will not give you what you want.

Even so, don't give up yet. The difference of clones is not a clone but may be useful. You might show that a member of the unary grade either has finitely many zeros or has some property Q, where Q is preserved by the clone generating scheme. Now the hope is to find a helpful property Q which is something that you can demonstrate g does not have.

I realize the above is just an abstract nonsense version of what you already know, but it might be a useful shift in perspective for you.

Gerhard "Ask Me About System Design" Paseman, 2012.10.16

Answer by Gerhard Paseman for The Inverse of the Euler Totient Function

2012-10-13T04:18:04Z

Here is a naive attempt, which can be refined to give an upper bound on the cardinality. I will only look at the case that the inverse n is odd, the even case being mildly more complicated.

So given $p$, I want to find how many odd $n$ satisfy $\phi(n)=p$. Let $p=r2^w$ with $r$ odd. To make things interesting assume $w>0$. Pick $b \geq w$ and assume $n$ has at most $b$ factors. Place the $w$ 2's in $b$ buckets. If a prime factor $q$ of $r$ is not going into a bucket, then we must put in one bucket enough to make $q-1$. Otherwise, distribute the prime factors of $r$ into the buckets. Each bucket will contain those primes which multiply to form $q-1$, where $q$ is a factor of $n$. If $r$ has $c$ not necessarily distinct prime factors, there are then at most $c^{b+1}$ ways to distribute the factors of $r$, and not all of them will work.

A recursive version is to assume the least prime factor of $n$ is $q$, and then try to find solutions to $\phi(m)=p/[(q-1)q^s]$ for appropriate values of $s$. This may be quicker to implement but harder to analyze.

Gerhard "Ask Me About System Design" Paseman, 2012.10.12

Answer by Gerhard Paseman for A weird function related to the denominators of rational squares

2012-10-12T18:38:46Z

I think pulling the parts of the range of the square function back to an interval decorated with Farey fractions will help not only with sigma, but also with the question with chi corresponding to the cube or other monotonic polynomial on the positive integers in place of sigma. Sigma is nice to study because there are about (k^2)/3 Farey fractions with denominator at most k, almost ensuring a bound of k for sigma(a) when k^2< a < (k+1)^2. I'll leave a similar bound for higher orders for you to derive.

Even just looking at (k +/- 1/t)^2 for positive integers t helps one understand the behavior of sigma near sigma(k^2); a similar idea was what motivated my comments below.

I do not know where your function has been studied, but I see connections to Farey fractions, rational approximation, and even discrete dynamical systems. Perhaps some of those areas, combined with a suggestion from elsewhwere, will give you what you seek.

Gerhard "Ask Me About System Design" Paseman, 2012.10.12

Comment by Gerhard Paseman

2013-02-05T20:14:06Z

Perhaps the problem is more basic. I will edit after the light dawns and fills the corners of my cranium. Gerhard "Quantifier Application Is Not Commutative" Paseman, 2013.02.05

Comment by Gerhard Paseman

2013-02-05T20:05:27Z

OK. I'm in trouble now. Please help. ab= b^ra=a^rb^r =ba since rth powers commute. Or do they? Gerhard "Shouldn't Be Using Martin's Definition?" Paseman, 2013.02.05

Comment by Gerhard Paseman

2013-02-05T19:47:10Z

I speak hastily, of course. All of the above is for classes of semigroups which share the same r. So I not only assume that r is the same for all a and b (minor quibble, as for a finite semigroup I can take R something like product or max of all r), but also every semigroup in the class uses the same r (not so minor). Gerhard "Now Return To Regular Programming" Paseman, 2013.02.05

Comment by Gerhard Paseman

2013-02-05T19:41:18Z

After spending two more minutes thinking, I see we can take w to be not only squarefree but of length 1. Thus either I am very confused, or we have that quasicommutative semigroups form a locally finite variety. Gerhard "Has Been Very Confused Before" Paseman, 2013.02.05

Comment by Gerhard Paseman

2013-02-05T17:47:23Z

Quid, his specification is not explicit enough: some of the requirements have to be inferred from the phrase "Big Data". Either n will be large or k will be large or both. In either case, I see it as compressing an array of k binary strings of n bits. For ease of discussion, I assume a skewed distribution of array values, so that the most common entries are stored using d bit codes for each common value, with d much smaller than n. The problem is a common one in CS and industry, with a variety of solutions. Gerhard "Ask Me About System Design" Paseman, 2013.02.05

Comment by Gerhard Paseman

2013-02-05T17:20:52Z

Look up dictionary compression. Especially in the case that k is much greater than 2^n, the idea is to encode common bit vectors by a shorter string that uses fewer than n bits, and use longer strings for combinations that are less rare. This works primarily if the distribution of patterns is far from uniform. For a scheme that works for all possible distributions, bit-vectors are liikely the way to go. Gerhard "Ask Me About Saving Memory" Paseman, 2013.02.05

Comment by Gerhard Paseman

2013-02-05T06:59:59Z

This foum is not a good fit for your question. You might try math.stackexchange or artofproblemsolving. Hint. Let z be a root of p(x). If p divides f then z is a root of f(x). Now rewrite f(z) using that idea and also that p(z)=0. Gerhard "What Does That Tell You?" Paseman, 2013.02.04

Comment by Gerhard Paseman

2013-02-05T05:27:00Z

Aaron's suggestion makes me think that there is a reduction from the Frobenius coin problem to this one. However, the reduction I am thinking of is exponential; it may be that doing a reduction in the other direction will yield a polynomial time solution (to borrow Aaron's example, polynomial in 6, 10 and 15 and not polynomial in their logs). I don't see such a reduction being more clever than Aaron's adjacency matrix suggestion. Gerhard "Reduce, Recycle, And Reuse Mathematics" Paseman, 2013.02.04

Comment by Gerhard Paseman

2013-02-04T20:34:17Z

With just a modest amount of being charitable Emil, I see implicit in the question something similar to "What is a weak first-order theory or other logical theory that doesn't need calculus or modern machinery to do what I ask about and that is close to something Archimedes could have used?" . A logical perspective on formal systems that model reasoning in ancient times might help with this and similar questions of interest. Gerhard "That's How I See It" Paseman, 2013.02.04

Comment by Gerhard Paseman

2013-02-04T06:18:42Z

Consider the cycle q=(1 2 3 ...n) on the set of columns of an order n matrix over F_2 with n > 1. Let Q=q applied to the order n identity matrix, so the main diagonal is shifted "out of the way". In addition to the n(n-1) matrices I + E_ij for i distinct from j, take also the n matrices Q + E_ii. I think this or a slight modification to resolve parity issues should work as a basis in characteristic 2. Gerhard "Ask Me About System Design" Paseman, 2013.02.03

Comment by Gerhard Paseman

2013-02-03T08:26:43Z

I can see that being handy when one needs to call out some of the indices. For your example from Bourbaki, I would sooner use X decorated with a hat or overbar to indicate a tuple. Gerhard "That May Just Be Me" Paseman, 2013.02.03

Comment by Gerhard Paseman

2013-02-03T08:12:18Z

While correct etiquette is being determined, MathOverflow as a medium should be mentioned, and the bibliography or reference section of the resulting paper should cite the question and/or answer that contributed. Some examples of this exist, see the meta thread of success stories. Note that such reference preserves whatever anonymity the entity has, and that entity can later reveal itself as it desires. There is also the benefit and credit due to the forum, its creators, and its community. Gerhard "Ask Me About System Design" Paseman, 2013.02.03

Comment by Gerhard Paseman

2013-02-03T05:09:30Z

I remember attending a MSRI conference in a previous millenium on universal algebra and category theory. I was wondering if a religious battle would break out over the notion of an empty algebra. Fortunately no blood was shed at that conference over the issue. This post reminds me of those years. Tom, I'm afraid I dealt more with nonempty algebras than potentially empty relational structures, so I am not entirely convinced by your comment. Not that you should worry. Gerhard "Pronounces Tom Devoid Of Blame" Paseman, 2013.02.02

Comment by Gerhard Paseman

2013-02-02T16:40:40Z

If you aren't picky, choosing base 1 or some irrational base will likely work. I don't think you should invent a term like "oneier" though. Gerhard "Inventing Words Is Sorta Fun" Paseman, 2013.02.02

Comment by Gerhard Paseman

2013-02-02T06:27:22Z

I think my point is that some view games mathematically, for the goal of practicing mathematics. While I understand and often sympathize with such an endeavour, I remind you that some games are for pure social entertainment, and mathematical analysis is often counter to that goal. I would consider a semiotic approach to Charades analysis, and I am not clear what goals your suggested approach are trying to reach. Gerhard "Likes Board Over Party Games" Paseman, 2013.02.01