Wikipedia:Reference desk/Archives/Mathematics/2021 July 9

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

July 9

What's wrong in what should be a simple calculation?

I'm trying to solve: $5e^{2z+4}-8=0$

If I try: $ln(e^{2z+4})=ln(8/5)$

$2z+4=ln(8/5)$

$(ln(8/5)-4)/2$

I get:

$-1.7649981853771322$

But if I follow this route:

$e^{10z+20}=8$

$ln(e^{10z+20})=ln8$

$10z+20=ln8$

$(ln8-20)/10$

I get:

$-1.7920558458320166$

Where is my mistake? --Bumptump (talk) 00:42, 9 July 2021 (UTC)

I think the right-hand-side of your second line should be log(8)/5, not log(8/5). Bubba73 ^{You talkin' to me?} 00:46, 9 July 2021 (UTC)

But:

$5e^{2z+4}-8=0$

is equal to:

$e^{2z+4}=8/5$

and then you would get:

$ln(e^{2z+4})=ln(8/5)$

not

$(ln8)/5$ on the right side.--Bumptump (talk) 01:20, 9 July 2021 (UTC)

I don't think you can multiply by 5 the way you did in the second one. Bubba73 ^{You talkin' to me?} 02:01, 9 July 2021 (UTC)

$5e^{2z+4}=e^{ln5+2z+4}\neq e^{10z+20}$. Ruslik_Zero 07:10, 9 July 2021 (UTC)

Nice mind-reading, Ruslik. (To answer the question actually posed: both calculations are correct, neither one contains an error.) By the way, LaTeX knows \ln, it will make everything look nicer: $\ln(8/5)$ etc. --JBL (talk) 22:39, 9 July 2021 (UTC)

Listing maximal independent sets in hypergraphs.

Let (V, E) be a hypergraph, in other words E is a subset of P(V). Call a subset S of V independent if it contains no element of E. When (V, E) is an ordinary graph, that is when all elements of E have two elements, this definition is consistent with the graph theory definition of an independent set. I'm looking for a simple but efficient way of listing the maximal independent sets. For ordinary graphs, the Bron–Kerbosch algorithm seems to work well for this when it's applied to the complement graph of (V, E). Perhaps there is a variation on it which also works for hypergraphs. I know there has been a lot of work done on independent sets in regular hypergraphs, but that's not applicable for what I need.

The situation is the following, I have a finite set V and an upper set P in P(V). (In other words if S⊇T∈P then S∈P.) It follows that the the compliment Q of P is a lower set. Membership in P is not easy to determine, so I'd like a list of minimal elements of P, say E, that way I can just check if any elements of E are in the set, if so then it's in P. The problem is knowing whether there are any minimal elements of P not already listed in E. If there is one then it must be independent in (V, E). It seems a lot easier to just check the maximal independent sets than to check all of P(V). Right now I'm treating this like an integer programming program, which is working for now. But every time I find a new minimal element of P and add it to E, it adds another constraint to the problem, and I don't know how many minimal elements there are likely to be. So I feel there must be a more appropriate approach. --RDBury (talk) 15:46, 9 July 2021 (UTC)

Perhaps rather than re-inventing the wheel you could use existing software? For example, Sage has built-in functions order_filter() (to return the upper set generated by a subset of a given poset) and minimal_elements() (to return the minimal elements of a given poset), see [1]. --JBL (talk) 01:29, 12 July 2021 (UTC)

@JayBeeEll: Thanks for the suggestion, Sage looks like something I should have on my computer regardless. It sounds like it wants to put the entire poset in memory though, and I have a feeling my computer will balk at having to deal with such a large amount of data. I generally don't have a problem with reinventing the wheel in any case; I rather know, at least theoretically, what's going in inside the black box before relying on it too much. I did roll my own IP solver, though calling it a solver is probably a stretch, more like an integer based LP solver with a Gomory cut attachment. It seems to work for what I'm doing though, at least for now. --RDBury (talk) 13:01, 12 July 2021 (UTC)

@RDBury: Yes, Sage is wonderful (I use it a lot in my research) though like all open-source projects what it's best at depends very much on random features of the developer community. I don't do a huge amount of poset stuff, but my impression was that Sage allows specifications of posets that are much more compact than a list of all elements and relations. But ultimately it is necessary to somehow specify the elements of the poset, which I guess is your original problem. (You've been a bit cryptic about what it means that you "have" a poset P.) --JBL (talk) 15:43, 14 July 2021 (UTC)

@JayBeeEll: The poset is simply P(V) ordered by inclusion, but let's say V is large enough that storing 2^|V| elements will be "inconvenient". That's why I was thinking IP/LP; you can represent a |V|-dim cube as a tableau with O(|V|²) entries rather than as a table of size O(2^|V|). Bron–Kerbosch has a similar property; even if the output size may be exponential in |V|, the storage requirement is reasonable. But I was rather vague about the collection P; I don't think details are necessary, since you can just say that P consists those elements of V which contain some element of a fixed collection S. --RDBury (talk) 19:02, 14 July 2021 (UTC)

Sage certainly knows what the Boolean lattice is (it's part of the catalogue of standard posets and lattices) and I am very skeptical that it loads the entire exponentially many vertices into memory upon invoking it (but again, I haven't personally experimented). I would like to try to say something more helpful but again you're very vague about what information you have. Is S an explicit list that you have access to? If so, it seems like your question is trivial (E = S, or perhaps E = S.minimal_elements() when we view S as a sub-poset of the Boolean lattice, and testing membership of X in P is testing whether any set in S is a subset of X). So presumably not. But then it is again not clear what it means that you "have" P, so not clear what kind of calculations you can make reasonably. (Here are some ways that a person might present a poset: as a complete list of vertices and relations; as a complete list of vertices and a minimal set of relations (a Hasse diagram); as a complete list of vertices and a not-necessarily-minimal-but-not-necessarily-complete list of relations; as an online data stream produced by an oracle, where each new vertex is presented along with its covers among previously introduced vertices; as a combination (disjoint sum, product, ordinal sum, ...) of some explicit simpler posets; as a function which, when called on two vertices, tells you whether the first is larger than the second, with the vertex set only given implicitly as the domain of the function; as an upper or lower set of some other poset, with explicitly specified minimal or maximal elements; more generally as a subposet of some other poset, consisting of those elements that satisfy a certain property (what kind of property?); .... Some algorithms will work efficiently for posets presented in one of these ways but not efficiently or not at all for posets presented in other ways.) --JBL (talk) 20:27, 14 July 2021 (UTC)

If P is the collection of sets that contain some element of a collection S, then the minimal elements of P is easy to find. But I'm looking for the maximal elements in the compliment of P. For example, if G is a graph, and S is the set of pairs {a, b} so that a and b are not connected in G, then P is the set of non-cliques, and it doesn't require an algorithm to find the its minimal sets, since it's just S. But the complement of P is the set of cliques, and finding the set of maximal cliques is what the BK algorithm does. Another problem of this type is to list maximal cap sets in the affine space Z₃ⁿ. Here, the collection S consists of colinear triples, but I'm looking for maximal sets which don't contain any of these. Note that I don't just want the sets which have the maximum possible number of elements, but all sets M any point not in M is colinear with a pair of point in M. Both of these examples are based on uniform hypergraphs, but I want to know if there is an algorithm which works for any hypergrapn. It's a very general problem, which is why I don't feel it's necessary to go into specifics on what I'm trying to do; I'd like to know if there is a general solution, not just a solution for one particular hypergraph. --RDBury (talk) 06:11, 15 July 2021 (UTC)

Oh, I see, you're trying to compute the rowmotion of your order ideal (or maybe the dual); see [2]. --JBL (talk) 14:16, 15 July 2021 (UTC)

That's close, but, assuming I understand the definitions, it's not quite the same. It's a very interesting and surprising result that the rowmotion is a permutation. I computed it for the lattice of ideals in P({0, 1, 2}), it turns out to be a regular permutation of order 5 on the 20 elements. It seems like we ought to have an article about it, but I'm not the one to write it. But the function I'm looking at is just the complement, which maps lower sets to upper sets and back. So given a lower set P generated by maximal elements S, find the minimal elements in V\S. You could use this information to generate the rowmotion, but going the other way seems like returning to the original problem: Given an ideal not given by a set a generators, find its maximal elements. Apparently, at least according to the language used in the WP articles, there is a difference between an lower set and an ideal(/filter) in that ideals are closed under joins. It's confusing to me because, as I mentioned below, as I remember it the term order ideal only required the lower set property. It looks like Sage uses order ideal to mean what I'm used to it meaning, which is what WP calls a lower set. At least so I gather from the example given in the SageMath post. --RDBury (talk) 22:33, 16 July 2021 (UTC)

I believe a that a suitable generalization of the Bron-Kerbosch algorithm should work for finding maximal independent sets of a hypergraph. Alternatively, even simpler (but with a potentially higher runtime): Start with a list containing the "independent sets" of single elements of V. With each step, add elements of V to the list of known independent sets in all possible ways and check which of the resulting sets are independent. If an independent set cannot be extended with an additional element, declare it maximal, output it, and ignore it evermore; else, replace it with the larger independent sets created by extending it with a single element in all possible ways. Repeat until every independent set discovered has been declared maximal.

Also, I noticed that you stated that you decided to treat the problem of finding minimal elements of the upper set P (whatever that is) as an integer linear programming problem, which, to me, unless I am very stupid, seems like a very strong indicator that P is a highly structured set (e.g. a set defined by some system of linear inequalities, or w/e). Is there in fact a special structure to this upper set P that you are interested in? Duckmather (talk) 19:49, 14 July 2021 (UTC)

That's a bit like what I'm doing now except I'm not being as automated about it. Just start with a random point, and keep adding vertices which do not cause an edge to be included until it's not possible to do so. I'm using LP/IP to narrow down the list of possible candidate points to add at each step. The result will either be a new independent set, or, since I'm not sure that my list of edges is complete, I may get a set with a an undiscovered edge. Then I can do the process in reverse, remove points one by one until I get a new minimal element of P, which I can then add to the list of edges.

I included a definition of 'upper set', and a link to the article, in the first post. I seem to remember that they were called 'order ideals' but apparently that term is being used for something else now. You don't need a lot of structure to turn a combinatorial problem into a IP problem, For example, if you want to look all sets that do not contain a set s, you can write this as a linear constraint s⋅x ≤ |s|-1. Here, the sets s and x are interpreted as 0-1 vectors, so s⋅x = |s∩x|. --RDBury (talk) 12:01, 15 July 2021 (UTC)

Galois field optimizations

Relating to the optimization of certain GF(2) operations, in particular both multiplication and modular division imply (at the very least) a time complexity on the order of O(N^2) and thus rather impractical to calculate for large N. Are there any methods for bringing that just a little closer to O(N)? And moreover can these two operation be combined somehow (ie: A * B mod C)? Just trying to improve the runtime here as it's currently very, very slow! Earl of Arundel (talk) 21:36, 9 July 2021 (UTC)

GF(2) is finite, thus operations on it have constant time complexity. Did you mean the polynomial ring over GF(2)?

If so, see Multiplication_algorithm#Fast_multiplication_algorithms_for_large_inputs: most of those algorithms can be adapted to the polynomial ring over GF(2).

On the low level, the CLMUL instruction set was made for this. --116.86.4.41 (talk) 14:13, 10 July 2021 (UTC)

As for the modulo part, this article (which was linked as a reference in CLMUL instruction set) contains an algorithm for that. --116.86.4.41 (talk) 14:21, 10 July 2021 (UTC)

Wow, I had no idea there were special CPU instructions for that! I'm actually using a scripting language in this case. You are right though, it does appear that algorithms such as Karatsuba and FFT should be adaptable to polynomial rings. Earl of Arundel (talk) 01:28, 11 July 2021 (UTC)

For small N (typically N=8 in computer applications) you multiply by precomputing logarithm and antilog tables, so a⋅b=antilog(log(a)+log(b)). For larger N, maybe you can split the numbers into smaller chunks and combine using the distributive law plus the log/antilog scheme. 2602:24A:DE47:BA60:8FCB:EA4E:7FBD:4814 (talk) 16:36, 10 July 2021 (UTC)

Sounds interesting! But how do you possibly compute an exact natural logarithm without truncation over GF(2)? (Do I use the log2(x) value in conjuction with something else perhaps?) Earl of Arundel (talk) 01:28, 11 July 2021 (UTC)

By logarithm I mean a discrete logarithm in the Galois field with regard to some generator g. I.e. let g be a generator of the field's multiplicative subgroup and x be an element of the field. Then y=log(x) if g**y = x. See: Finite_field#Discrete_logarithm 2602:24A:DE47:BA60:8FCB:EA4E:7FBD:4814 (talk) 06:21, 11 July 2021 (UTC)

Ah, right. Thanks for the clarification! Earl of Arundel (talk) 23:01, 11 July 2021 (UTC)