## What does Arg {Inf I(d)} means?

I am currently studying the phase-field method for fracture modeling. In an article by Miehe -“Thermodynamically consistent phase-field models of fracture: Variational principles and multi-field FE implementation”, I came across on an identity that I don’t understand basically it says:

enter image description here

Can anyone tell me what does that mean? I added image because I don’t know how to add this identity in another way.

# Set Inclusion

GIVEN: set of cards, some with blue backs, and each with a positive, integer face value.

QUESTION: Are there any [blue-backed cards] with a [face value <= L]?

• 2 independent variables: [blue/white cards], [integer face values]

Function A: Select a blue-backed card

• face value depends on which card you select
• each blue card potentially has face value <= L
• thus, worst-case = [check all blue cards]

Function B: Select a face value <= L

• blue back depends on which card you select
• each card w/ face value <= L potentially has blue back
• thus, worst-case = [check all cards w/ face value <= L]

Function B cannot exist. There is no way to verify that a selected card has a blue back, since don’t know key info:

• How are cards marked with a blue back?

WORST-CASE: turn over all blue-backed cards (Function A)

# Travelling Salesman

GIVEN: complete graph, G(V,E), where all edges are positive, integer values.

DEFINITION: “config”

• {A, B, u, v} where u & v are 2 vertices, and A & B are the remaining vertices split up as evenly as possible

DEFINITION: “optimal tour of a config”

• shortest path from u to v, only going thru each vertex in A once, and
• shortest path from v to u, only going thru each vertex in B once

Assume we have a function, f, that returns the optimal tour for a given config, in constant time.

A smallest tour must be the optimal tour of one of the configs in G.
Any config could produce the smallest tour.

NOTE: Each tour is an edge-set that can form |V|/2 or |V| configs, for even or odd |V|, respectively.

A COMPLETE GRAPH is equivalent to: set of cards, some with blue backs, and each with a positive, integer face value.

• each card represents a set of edges with size = |V|
• blue backs mark any edge-sets that are an optimal tour for a config
• face value is the sum of the edge-set represented by the card

QUESTION: Are there any [blue-backed cards] with a [face value <= L]?

• 2 independent variables: [blue/white cards], [integer face values]

Consider case where L = length of smallest tour.

• Only need look at blue cards (edge-sets that are an optimal tour for a config)
• Only need look at cards w/ face value = L (edge-sets with sum = L)

Function A: Select blue-backed card

• face value depends on which card you select
• each blue card potentially has face value = L
• thus, worst-case = [check all blue cards]

Function B: Select a card with face value = L

• blue back depends on which card you select
• each card w/ face value = L potentially has blue back
• thus, worst-case = [check all cards w/ face value = L]

Unlike “Set Inclusion”, now you can verify that a selected card for Function B has a blue back, by running f on the selected card’s configs.

However, controlling either variable, [choosing blue card] or [choosing card w/ face value = L], causes the other to be uncontrollable.

WORST-CASE:

• FACE-DOWN Approach: turn over all cards with blue back (Function A)
• FACE-UP Approach: turn over all cards with face value = L (Function B)

So the final question: Is TSP-Decision a version of “Set Inclusion” that has enough information to define a Function B?

If so, does this mean that the worst-case running time of TSP-Decision is lower-bounded by the smaller of the 2 domains of Functions A and B? i.e. min{number of blue cards, number of cards with face value = L} — still only for the case where L = length of smallest tour.

## Derivation of Perceptron weight update formula

I’ve started out studying Machine Learning and am currently reading up about how a single perceptron works. From the wikipedia page, my understanding is as follows: suppose we have an input sample $$\mathbf{x} = [x_1, \ldots, x_n]^T$$, an initial weight vector $$\mathbb{w} = [w_1, \ldots, w_n]^T$$. Let the true output corresponding to $$\mathbf{x}$$ be $$y’$$.

The output given by the perceptron is $$y = f(\sum_{i=0}^n w_ix_i)$$, where $$w_0$$ is the bias and $$x_0=1$$. If $$\eta$$ is the learning rate, the weights are updated according to the following rule: $$\Delta w_i = \eta x_i(y’-y)$$

This is according to wikipedia. But I know the weights are updated on the basis of the gradient descent method, and I found another nice explanation based on the gradient descent method HERE. The derivation there results in the final expression for weight update:

$$\Delta w_i = \eta x_i(y’-y)\frac{df(S)}{dS}$$

where $$S = \sum_{i=0}^{n}w_ix_i$$. Is there a reason why this derivative term is ignored? There was another book that mentioned the same weight update formula as Wikipedia, without the derivative term. I’m pretty sure we can’t just assume $$f(S) = S$$.

## Conditional expectation with respect to a sigma algebra

As part of a more complex problem I have this passage: $$E(X_{n+1}-X_{n}|F_{n})=E(X_{n+1}-X_{n})$$ where $$X_{n}$$ is a random variable defined as $$X_n(w)= \begin{cases} 0 \quad \frac{1}{n} < w \leq 1 \ n-n^2w \quad 0 \leq w \leq \frac{1}{n} \end{cases}$$ and $$F_n=\sigma(X_{1},…,X_{n})$$ is the sigma algebra generated by $$X_{1},…,X_{n}$$

Now I understand intuitively why this is true but is it possible to prove it in a rigorous way? I know that I can use the law of iterated expectation to get away with it but I want to understand why $$X_{n+1}-X_{n}$$ is independent from $$F_{n}$$.

## Need help understanding what co-recursively enumerable means

Lets say I have a set: $$L = \{\langle G \rangle | L(G) = \sum^{\star}\}$$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not halt on inputs in L.

So in this case would something “not in L” be nothing?

## transformation between two formulations of the mincost flow problem

According to this slide, the following two formulations of the mincost flow problem are equivalent:

Given directed graph G = (V, E)

• Let u denote capacities
• Let c denote edge costs.
• A flow of f(v,w) units on edge (v,w) contributes cost c(v,w)f(v,w) to the objective function.

1. Send x units of flow from s to t as cheaply as possible.

2. General version with supplies and demands

• No source or sink.
• Each node has a value b(v).
• positive b(v) is a supply
• negative b(v) is a demand.
• Find flow which satisfies supplies and demands and has minimum total cost.

I can see that 2. is a special case of 3. in which only two nodes (s and t) and have non-zero demand. But I cannot figure out how to transform the more general problem 3. into problem 2.

Can anyone help explain how to transform 3. to 2. ?

That is, how to e.g. add edges and/or change capacity/cost, to solve problem 3. with a solver of problem 2.

## Is there any theorem connect to this problem?

It is a question I always ask when I was a primary student:

Could a number only contains digit’1′ with $$p$$ digits writes $$A=\frac{10^{p}-1}{9} = \underbrace{11\cdots 1}_{p\text{ digits}}$$ be a prime?

When $$p$$ is not a prime, the factorization of $$A$$ is obvious, but if $$p$$ is a prime, the factorization of $$A$$ may be subtle.

Here I made a list of some result for prime $$p$$

$$\begin{array}{c|lcr} p & \ \text{factors} \ \hline 3 & 3 \times 37\ 5 & 41 \times 271 \ 7 & 239 \times 4649 \ 11 & 21649 \times 513239 \ 13 & 53 \times 79 \times 265371653 \ 17 & 2071723 \times 5363222357 \ 19 & \text{prime} \ 23 & \text{prime} \ 29 & 3191 \times 16763 \times 43037 \times 62003 \times 77843839397 \ 31 & 2791 \times 6943319 \times 57336415063790604359 \ 37 & 2028119 \times 247629013 \times 2212394296770203368013 \ 41 & 83 \times 1231 \times 538987 \times 201763709900322803748657942361 \ 43 & 173 \times 1527791 \times 1963506722254397 \times 2140992015395526641 \ 47 & 35121409 \times 316362908763458525001406154038726382279 \ 53 & 107 \times 1659431 \times 1325815267337711173 \times 47198858799491425660200071 \ 59 & 2559647034361 \times 4340876285657460212144534289928559826755746751 \ 61 & 733 \times 4637 \times 329401 \times 974293 \times 1360682471 \times 106007173861643 \times 7061709990156159479 \ 67 & 493121 \times 79863595778924342083 \times 28213380943176667001263153660999177245677 \ \end{array}$$

I am not major in number theory, just curious again if there is any theorem or former work on this kind of question.

## Finding the longest path in an undirected node-weighted tree

I have a tree where each node is assigned a weight (a real number that can be positive or negative). I need an algorithm to find a simple path of maximum total weight (that is, a simple path where the sum of the weights of the nodes in the path is maximum). There’s no restriction on what node the path starts or ends.

I have a possible algorithm, but I am not sure it works and I am looking for a proof. Here it is:

1)Select an arbitrary node u and run DFS(u) to find the maximum weight simple path that starts at u. Let (u, v) be this path.

2)Run DFS(v) to find the maximum weight simple path that starts at v. Let this path be (v, z).

Then (v, z) is a simple path of maximum weight. This algorithm is linear in the size of the graph. Can anyone tell me if it works, and if so, give a proof?

Note: The Longest Path Problem is NP-Hard for a general graph with cycles. However, I only consider trees here.

## Superposition calculus: Elimination of redundant atoms

Bachmair and Ganzinger (1991), ‘Rewrite-Based Equational Theorem Proving With Selection and Simplification’, section 5.2, ‘Simplification and Deletion Techniques’, page 17, ‘Elimination of redundant atoms’, discusses the question of when, having used one clause to derive another, you can throw away the first clause instead of ending up with both. As discussed in Redundancy elimination in the superposition calculus you cannot do this in the general case, but you can do it in some particular cases, such as when discarding tautologies or subsumed clauses.

“Let C = Γ, u ≈ v → ∆ be a clause in N. If N |= Γ → u ≈ v, ∆, then N |= Γ → ∆, so that C can be simplified to Γ → ∆. A particular case is the elimination of multiple occurrences of atoms in the antecedent. For example, if C = Γ, u ≈ v, u ≈ v → ∆, then the clause Γ, u ≈ v → u ≈ v, ∆ is a tautology and hence trivially implied by N. Redundant atoms in the succedent can be eliminated in a similar way.”

Hang on. “elimination of multiple occurrences of atoms in the antecedent”, “Redundant atoms in the succedent can be eliminated” – it would certainly be nice if you could do this, but as I understand it, as discussed in https://stackoverflow.com/questions/29164610/why-are-clauses-multisets you have to treat clauses as multisets, not sets, you cannot just throw away multiple occurrences of the same atom. What am I missing?

And “then the clause Γ, u ≈ v → u ≈ v, ∆ is a tautology” – as I understand it, this is true, a clause which contains both an item and its negation is indeed a tautology and you really can promptly discard tautologies, but what does that have to do with multiple occurrences of the same atom with the same polarity? How is that sentence connected to the rest of the paragraph?

## Definition of Borel Field and Sigma Algebra

Are these terms equivalent?

• borel algebra
• borel sigma-algebra
• borel sigma-field
• a sigma-algebra generated by a topology
• borel field

(If a set is sigma-algebra, there exists a topology that generates the sigma-algebra, so any sigma-algebra is a borel sigma-algebra?)

By Chung’s A Course in Probability Theory, a borel field is defined as

• closed under complement
• closed under countable union
• closed under countable intersection

which looks like the definition of sigma-algebra. Are these also equivalent terms?

• borel field
• sigma-algebra
• sigma-field

According to http://mathworld.wolfram.com/BorelField.html, the definition of borel field does not require a set is closed under complement. Which definition is correct?

According to Is Borel-field different from $$\sigma$$-field?, are borel-* terms only used in terms of real space?