text:
# Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks

Graph neural networks (GNN) have shown great advantages in many graph-based learning tasks but often fail to predict accurately for a task-based on sets of nodes such as link/motif prediction and so on. Many works have recently proposed to address this problem by using random node features or node distance features. However, they suffer from either slow convergence, inaccurate prediction, or high complexity. In this work, we revisit GNNs that allow using positional features of nodes given by positional encoding (PE) techniques such as Laplacian Eigenmap, Deepwalk, etc. GNNs with PE often get criticized because they are not generalizable to unseen graphs (inductive) or stable. Here, we study these issues in a principled way and propose a provable solution, a class of GNN layers termed PEG with rigorous mathematical analysis. PEG uses separate channels to update the original node features and positional features. PEG imposes permutation equivariance w.r.t. the original node features and rotation equivariance w.r.t. the positional features simultaneously. Extensive link prediction experiments over 8 real-world networks demonstrate the advantages of PEG in generalization and scalability.

• 1 publication
• 7 publications
• 19 publications
• 63 publications
06/11/2019

### Position-aware Graph Neural Networks

Learning node embeddings that capture a node's position within the broad...
08/20/2020

### A comparative study of similarity-based and GNN-based link prediction approaches

The task of inferring the missing links in a graph based on its current ...
11/22/2020

### Revisiting graph neural networks and distance encoding in a practical view

Graph neural networks (GNNs) are widely used in the applications based o...
08/23/2021

### Integrating Transductive And Inductive Embeddings Improves Link Prediction Accuracy

In recent years, inductive graph embedding models, viz., graph neural ne...
12/26/2020

### Graph neural network based approximation of Node Resiliency in complex networks

The emphasis on optimal operations and efficiency has led to increased c...
06/11/2021

### Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns

Graph neural networks (GNNs) have achieved tremendous success on multipl...
02/22/2021

### MagNet: A Magnetic Neural Network for Directed Graphs

The prevalence of graph-based data has spurred the rapid development of ...

## 1 Introduction

Graph neural networks (GNN), inheriting from the power of neural networks (hornik1989multilayer)

, have recently become the de facto standard for machine learning with graph-structured data

(scarselli2008graph). While GNNs can easily outperform traditional algorithms for single-node tasks (such as node classification) and whole graph tasks (such as graph classification), GNNs predicting over a set of nodes often achieve subpar performance. For example, for link prediction, GNN models, such as GCN (kipf2016semi), GAE (kipf2016variational)

may perform even worse than some simple heuristics such as common neighbors and Adamic Adar

(liben2007link) (see the performance comparison over the networks Collab and PPA in Open Graph Benchmark (OGB) (hu2020open)). Similar issues widely appear in node-set-based tasks such as network motif prediction (liu2022neural; besta2021motif), motif counting (zhengdao2020can), relation prediction (wang2021relational; teru2020inductive) and temporal interaction prediction (wang2021inductive), which posts a big concern for applying GNNs to these relevant real-world applications.

The above failure is essentially induced by the loss of node identities during the intrinsic computation of GNNs. Nodes that get matched under graph automorphism will be associated with the same representation by GNNs and thus are indistinguishable (see Fig. 1

(i)). A naive way to solve this problem is to pair GNNs with one-hot encoding as the extra node feature. However, it violates the fundamental inductive bias, i.e., permutation equivariance which GNNs are designed for, and thus may lead to poor generalization capability: The obtained GNNs are not transferable (inductive) across different node sets and different graphs or stable to network perturbation.

Many works have been recently proposed to address such an issue. The key idea is to use augmented node features, where either random features (RF) or deterministic distance encoding (DE) can be adopted. Interested readers may refer to the book chapter (GNNBook-ch5-li) for detailed discussion. Here we give a brief review. RF by nature distinguishes nodes and guarantees permutation equivariance if the distribution to generate RF keep invariant across the nodes. Although GNNs paired with RF have been proved to be more expressive (murphy2019relational; sato2021random), the training procedure is often hard to converge and the prediction is noisy and inaccurate due to the injected randomness (abboud2020surprising). On the other hand, DE defines extra features by using the distance from a node to the node set where the prediction is to be made (li2020distance). This technique is theoretically sound and empirically performs well (zhang2018link; li2020distance; zhang2020revisiting). But it introduces huge memory and time consumption. This is because DE is specific to each node set sample and no intermediate computational results, e.g., node representations in the canonical GNN pipeline can be shared across different samples.

To alleviate the computational cost of DE, absolute positions of nodes in the graph may be used as the extra features. We call this technique as positional encoding (PE). PE may approximate DE by measuring the distance between positional features and can be shared across different node set samples. However, the fundamental challenge is how to guarantee the GNNs trained with PE keep permutation equivariant and stable. Using the idea of RF, previous works randomize PE to guarantee permutation equivariance. Specifically, you2019position designs PE as the distances from a node to some randomly selected anchor nodes. However, the approach suffers from slow convergence and achieves merely subpar performance. srinivasan2020equivalence states that PE using the eigenvectors of the randomly permuted graph Laplacian matrix keeps permutation equivariant. dwivedi2020generalization; kreuzer2021rethinking argue that such eigenvectors are unique up to their signs and thus propose PE that randomly perturbs the signs of those eigenvectors. Unfortunately, these methods are problematic. They fail to provide permutation equivariant GNNs when the matrix has multiple eigenvalues, which thus are dangerous when applying to many practical networks. For example, large social networks, when not connected, have multiple 0 eigenvalues; small molecule networks often have non-trivial automorphism that may give multiple eigenvalues. Even if the eigenvalues are distinct, these methods are unstable. We prove that the sensitivity of node representations to the graph perturbation depends on the inverse of the smallest gap between two consecutive eigenvalues, which could be actually large when two eigenvalues are close (Lemma 3.4).

In this work, we propose a principled way of using PE to build more powerful GNNs. The key idea is to use separate channels to update the original node features and positional features. The GNN architecture keeps not only permutation equivariant w.r.t. node features but also rotation equivariant w.r.t. positional features. This idea applies to a broad range of PE techniques that can be formulated as matrix factorization (qiu2018network) such as Laplacian Eigenmap (LE) (belkin2003laplacian) and Deepwalk (perozzi2014deepwalk). We design a GNN layer PEG that satisfies such requirements. PEG is provably stable: In particular, we prove that the sensitivity of node representations learnt by PEG only depends on the gap between the th and th eigenvalues of the graph Laplacian if -dim LE is adopted as PE, instead of the smallest gap between any two consecutive eigenvalues that previous works have achieved.

PEG gets evaluated in the most important node-set-based task, link prediction, over 8 real-world networks. PEG achieves comparable performance with strong baselines based on DE while having much lower training and inference complexity. PEG achieves significantly better performance than other baselines without using DE. Such performance gaps get enlarged when we conduct domain-shift link prediction, where the networks used for training and testing are from different domains, which effectively demonstrates the strong generalization and transferability of PEG.

### 1.1 Other related works

As long as GNNs can be explained by a node-feature-refinement procedure (hamilton2017inductive; gilmer2017neural; morris2019weisfeiler; velivckovic2018graph; klicpera2019predict; chien2021adaptive), they suffer from the aforementioned node ambiguity issue. Some GNNs cannot be explained as node-feature refinement as they directly track node-set representations (maron2018invariant; morris2019weisfeiler; chen2019equivalence; maron2019provably). However, their complexity is high, as they need to compute the representation of each node set of certain size. Moreover, they were only studied for graph-level tasks. EGNN (satorras2021n) seems to be a relevant work as it studies when the nodes have physical coordinates given in prior. However, no analysis of PE has been provided.

A few works studied the stability of GNNs by using tools like graph scattering transform (for graph-level representation) (gama2019diffusion; gama2019stability) and graph signal filtering (for node-level representations) (levie2021transferability; ruiz2020graphon; ruiz2021graph; gama2020stability; nilsson2020experimental). They all focus on justifying the stability of the canonical GNN pipeline, graph convolution layers in particular. None of them consider positional features let alone the stability of GNNs using PE.

## 2 Notations and Preliminaries

In this section, we prepare the notations and preliminaries that are useful later. First, we define graphs.

###### Definition 2.1 (Graph).

Unless specified, we always consider undirected graphs of nodes and let . One such graph can be denoted as , where is the adjacency matrix. denotes the node features, where the th row, , is the feature vector of node . A graph may have self loops, i.e., has nonzero diagonals. Denote as the diagonal degree matrix where for . Let . Denote the normalized adjacency matrix as and the normalized Laplacian matrix as .

###### Definition 2.2 (Permutation).

An -dim permutation matrix is a matrix in where each row and each column has only one single 1. All such matrices are collected in , simplified as .

We denote the vector -norm as , the Frobenius norm as and the operator norm as .

###### Definition 2.3 (Graph-matching).

Given two graphs and their normalized Laplacian matrices for , their matching can be denoted by a permutation matrix that best aligns the graph structures and the node features.

 P∗(G(1),G(2))≜argminP∈Π∥L(1)−PL(2)PT∥F+∥X(1)−PX(2)∥F

Using instead of to represent graph structures is for notational simplicity. Actually for an unweighted graph, there is a bijective mapping between and . One can rewrite the first term with . Later, we use by not specifying and if there is no confusion. The distance between the two graphs can be defined as .

Next, we review eigenvalue decomposition and summarize arguments on its uniqueness in Lemma 2.6.

###### Definition 2.4 (Eigenvalue Decomposition (EVD)).

For a positive semidefinite (PSD) matrix , it has eigenvalue decomposition where is a real diagonal matrix with the eigenvalues of , as its diagonal components.

is an orthogonal matrix where

is the th eigenvector, i.e. .

###### Definition 2.5 (Orthogonal Group in the Euclidean space).

includes all -by- orthogonal matrices. A subgroup of includes all diagonal matrices with as the diagonal components, .

###### Lemma 2.6.

EVD is not unique. If all the eigenvalues are distinct, i.e., , is unique up to the signs of its columns, i.e., replacing by also gives EVD. If there are multiple eigenvalues, say , then lie in an orbit induced by the orthogonal group , i.e., replacing by for any while keeping eigenvalues and other eigenvectors unchanged also gives EVD.

Next, we define Positional Encoding (PE), which associates each node with a vector in a metric space where the distance between two vectors can represent the distance between the nodes in the graph.

###### Definition 2.7 (Positional Encoding).

Given a graph , PE works on and gives where each row gives the positional feature of node .

The absolute values given by PE may not be useful while the distances between the positional features are more relevant. So, we define PE-matching that allows rotation to best match positional features, which further defines the distance between two collections of positional features.

###### Definition 2.8 (PE-matching).

Consider two groups of positional features . Their matching is given by . Later, is used if it causes no confusion. Define the distance between them as .

## 3 Equivariant and Stable Positional Encoding for GNN

In this section, we will study the equivariance and stability of a GNN layer using PE .

### 3.1 Our Goal: Building Permutation Equivariant and Stable GNN layers

A GNN layer is expected to be permutation equivariant and stable. These two properties, if satisfied, guarantee that the GNN layer is transferable and has better generalization performance. Permutation equivariance implies that model predictions should be irrelevant to how one indexes the nodes, which captures the fundamental inductive bias of many graph learning problems: A permutation equivariant layer can make the same prediction over a new testing graph as that over a training graph if the two graphs match each other perfectly, i.e. the distance between them is 0. Stability is actually an even stronger condition than permutation equivariance because it characterizes how much gap between the predictions of the two graphs is expected when they do not perfectly match each other.

Specifically, given a graph with node features , we consider a GNN layer updating the node features, denoted as . We define permutation equivariance and stability as follows.

###### Definition 3.1 (Permutation Equivariance).

A GNN layer is permutation equivariant, if for any and any graph , .

###### Definition 3.2 (Stability).

A GNN layer is claimed to be stable, if there exists a constant , for any two graphs and , letting denote their matching, satisfies . By setting and for some , the RHS becomes zero, so a stable makes the LHS zero too. So, stability is a stronger condition than permutation equivariance.

Our goal is to guarantee that the GNN layer that utilizes PE is permutation equivariant and stable. To distinguish from the GNN layer that does not use PE, we use to denote a GNN layer that uses PE, which takes the positional features as one input and may update both node features and , i.e., . Now, we may define PE-equivariance and PE-stability for the GNN layer .

###### Definition 3.3 (PE-stability & PE-equivariance).

Consider a GNN layer that uses PE. When it works on any two graphs , and gives , let be the matching between the two graphs. is PE-stable, if for some constant we have

 ∥^X(1)−P∗^X(2)∥F+η(^Z(1),P∗^Z(2))≤Cd(G(1),G(2)). (1)

Recall measures the distance between two sets of positional features as defined in Def. 2.8. Similar as above, a weaker condition of PE-stability is PE-equivariance: If and for some , we expect a perfect match between the updated node features and positional features, and .

Note that previous works also consider that updates only node features, i.e., . In this case, PE-stability can be measured by removing the second term on from Eq.1.

### 3.2 PE-stable GNN layers based on Laplacian Eigenmap as Positional Encoding

To study the requirement of the GNN layer that achieves PE-stability, let us start from a particular PE technique, i.e., Laplacian eigenmap (LE) (belkin2003laplacian) to show the key insight behind. Later, we generalize the concept to some other PE. Let denote LE, which includes the eigenvectors that correspond to the smallest eigenvalues of the normalized Laplacian matrix .

Previous works failed to design PE-equivariant or PE-stable GNN layers. srinivasan2020equivalence claims that if a GNN layer that does not rely on PE is permutation equivariant, PE-equivariance may be kept by adding to node features, i.e., , where MLP

is a multilayer perceptron that adjusts the dimension properly. This statement is problematic when

is not unique given the graph structure . Specifically, though sharing graph structure , if different implementations lead to different LEs , then , which violates PE-equivariance. srinivasan2020equivalence suggests using graph permutation augmentation to address the issue, which makes assumptions on an invariant distribution of and empirically does not work well.

dwivedi2020generalization; kreuzer2021rethinking claim the uniqueness of up to the signs and suggest building a GNN layer that uses random as where is uniformly at random sampled from . They expect PE-equivariance in the sense of expectation. However, this statement is generally wrong because it depends on the condition that all eigenvalues have to be distinct as stated in Lemma 2.6. Actually, for multiple eigenvalues, there are infinitely many eigenvectors that lie in the orbit induced by the orthogonal group. Although many real graphs have multiple eigenvalues such as disconnected graphs or graphs with some non-trivial automophism, one may argue that the methods work when the eigenvalues are all distinct. However, the above failure may further yield PE-instability even when the eigenvalues are distinct but have small gaps due to the following lemma.

###### Lemma 3.4.

For any PSD matrix without multiple eigenvalues, set positional encoding as the eigenvectors given by the smallest eigenvalues sorted as of . For any sufficiently small , there exists a perturbation , such that

 minS∈SN(p)∥PE(B)−PE(B+△B)S∥F≥0.99max1≤i≤p|λi+1−λi|−1∥△B∥F+o(ϵ). (2)

Lemma 3.4 implies that small perturbation of graph structures may yield a big change of eigenvectors if there is a small eigengap. Consider two graphs and , where and is with a small perturbation . The perturbation is small enough so that the matching . However, the change of PE even after removing the effect of changing signs could be dominated by the largest inverse eigengap among the first eigenvalues . In practice, it is hard to guarantee all these eigenpairs have large gaps, especially when a large is used to locate each node more accurately. Plugging this PE into a GNN layer gives the updated node features a large change and thus violates PE-stability.

PE-stable GNN layers.

Although a particular eigenvector may be not stable, the eigenspace, i.e., the space spanned by the columns of

could be much more stable. This motivates our following design of the PE-stable GNN layers. Formally, we use the following lemma that can characterize the distance between the eigenspaces spanned by LEs of two graph Laplacians. The error is controlled by the inverse eigengap between the th and th eigenvalues , which by properly setting is typically much smaller than in Lemma 3.4. We compute the ratio between these two values over some real-world graphs as shown in Fig. 2.

###### Lemma 3.5.

For two PSD matrices , set as the eigenvectors given by the smallest eigenvalues of . Suppose has eigenvalues and . Then, for any permutation matrix ,

 η(PE(B(1)),PPE(B(2)))≤232δmin{√p∥B(1)−PB(2)PT∥op,∥B(1)−PB(2)PT∥F} (3)

Inspired by the stability of the eigenspace, the idea to achieve PE-stability is to make the GNN layer invariant to the selection of bases of the eigenspace for the positional features. So, our proposed PE-stable GNN layer that uses PE should satisfy two necessary conditions: 1) Permutation equivariance w.r.t. all features; 2) Rotation equivariance w.r.t. positional features, i.e.,

 PE-stable layer cond. 1: (P^X,P^Z) =g(PAPT,PX,PZ),∀P∈Π(N), (4) PE-stable layer cond. 2: (^X,^ZQ) =g(A,X,ZQ),∀Q∈SO(p). (5)

Rotation equivariance reflects the eigenspace instead of a particular selection of eigenvectors and thus achieves much better stability. Interestingly, these requirements can be satisfied by EGNN recently proposed (satorras2021n) as one can view the physical coordinates of objects considered by EGNN as the positional features. EGNN gets briefly reviewed in Appendix F. Thm. 3.6 proves PE-equivariance under the conditions Eqs. 4 and 5.

###### Theorem 3.6.

A GNN layer that uses and satisfies Eqs. 4,5 is PE-equivariant if the th and th eigenvalues of the normalized Laplacian matrix are different, i.e., .

Note that satisfying Eqs. 4,5 is insufficient to guarantee PE-stability that depends on the form of .

We implement in our model PEGN with further simplification which has already achieved good empirical performance: Use a GCN layer with edge weights according to the distance between the end nodes of the edge and keep the positional features unchanged. This gives the PEG layer,

 PEG:gPEG(A,X,Z)=(ψ[(^A⊙Ξ)XW],Z),where Ξuv=ϕ(∥Zu−Zv∥), ∀u,v∈[N]. (6)

Here

is an element-wise activation function,

is an MLP mapping from and is the Hadamard product. Note that if is sparse, only for an edge needs to be computed.

We may also prove that the PEG layer satisfies the even stronger condition PE-stability.

###### Theorem 3.7.

Consider two graphs , . Denote their normalized Laplacian matrices’ th eigenvalue as and th eigenvalue as . Assume that . Also, assume that and in the PEG layer in Eq. 6 are , -Lipschitz continuous respectively. Then, the PEG layer that uses satisfies PE-stability with the constant in Eq. 1 as .

Note that to achieve PE-stability, we need to normalize the node initial features to keep bounded, and control and . In practice is typically satisfied, e.g. setting

as ReLU. Here, the most important term is

. PE-stability may only be achieved when there is an eigengap between and and the larger eigengap, the more stable. This observation may be also instructive to select the in practice. As previous works may encounter a smaller eigengap (Lemma 3.4), their models will be generally more unstable.

Also, the simplified form of is not necessary to achieve PE-stability. However, as it has already given consistently better empirical performance than baselines, we choose to keep using .

### 3.3 Generalized to Other PE techniques: DeepWalk and LINE

It is well known that LE, as to compute the smallest eigenvalues, can be written as a low-rank matrix optimization form , s.t. . Other PE techniques, such as Deepwalk (perozzi2014deepwalk), Node2vec (grover2016node2vec) and LINE (tang2015line) can be unified into a similar optimization form, where the positional features are given by matrix factorization ( may be asymmetric so may not be ) and satisfies

 M∗=argminM∈RN×NℓPE(A,M)≜tr(f+(A)g(M)+f−(D)g(−M)),s.t% .rank(M)≤p (7)

Here typically revises by combining degree normalization and a power series of , corresponds to edge negative sampling that may be related to node degrees, and

is a component-wise log-sigmoid function

. E.g., in LINE, , , for some positive constant , where is the all-one vector. More discussion on Eq.7 and the forms of and for other PE techniques are given in Appendix G.

According to the above optimization formulation of PE, all the PE techniques generate positional features based on matrix factorization, thus are not unique. always lies in the orbit induced by , i.e., if solves Eq.7, for solves it too. A GNN layer still needs to satisfy Eqs. 4,5 to guarantee PE-equivariance. PE-stability actually asks even more.

###### Theorem 3.8.

Consider a general PE technique that has an optimization objective as Eq.7, computes its optimal solution and decomposes , s.t. to get positional features . Essentially, consists of the right-singular vectors of . If Eq.7 has a unique solution , and therein satisfy and , then a GNN layer that satisfies Eqs. 4,5 is PE-equivariant.

Note that the conditions on and are generally satisfied by Deepwalk, Node2vec and LINE. However, solving Eq.7 to get the optimal solution may not be guaranteed in practice because the low-rank constraint is non-convex. One may consider relaxing the low-rank constraint into the nuclear norm for some threshold  (recht2010guaranteed), which reduces the optimization Eq.7 into a convex optimization and thus satisfies the conditions in Thm. 3.8

. Empirically, this step and the step of computing SVD seem unnecessary according to our experiments. The PE-stability is related to the value of the smallest non-zero singular value of

. We leave the full characterization of PE-equivariance and PE-stability for the general PE techniques for the future study.

## 4 Experiments

### 4.1 The Experimental Pipeline of PEG for Link Prediction

We use PEG to build GNNs. The pipeline contains three steps. First, we adopt certain PE techniques to compute positional features . Second, we stack PEG layers according to Eq. 6. Suppose the final node representations are denoted by . Third, for link prediction over , we concatenate denoted as and adopt MLP to make final predictions. In the experiments, we test LE and Deepwalk as PE, and name the models PEG-LE and PEG-DW respectively. To verify the wide applicability of our theory, we also apply PEG to GraphSAGE hamilton2017inductive by similarly using the distance between PEs to control the neighbor aggregation according to Eq. 6 and term the corresponding models PE-SAGE-LE and PE-SAGE-DW respectively.

For some graphs, especially those small ones where the union of link sets for training, validation and testing cover the entire graph, the model may overfit positional features and hold a large generalization gap. This is because the links used as labels to supervise the model training are also used to generate positional features. To avoid this issue, we consider a more elegant way to use the training links. We adopt a 10-fold partition of the training set. For each epoch, we periodically pick one fold of the links to supervise the model while using the rest links to compute positional features. Note that PEs for different folds can be pre-computed by removing every fold of links, which reduces computational overhead. In practice, the testing stage often corresponds to online service and has stricter time constraints. Such partition is not needed so there is no computational overhead for testing. We term the models trained in this way as PEG-LE+ and PEG-DW+ respectively.

Datasets.

We use eight real graphs, including Cora, CiteSeer and Pubmed

(sen2008collective), Twitch (RU), Twitch (PT) and Chameleon (rozemberczki2021multi), DDI and COLLAB (hu2021ogb). Over the first 6 graphs, we utilize 85%, 5%, 10% to partition the link set that gives positive examples for training, validation and testing and pair them with the same numbers of negative examples (missing edges). For the two OGB graphs, we adopt the dataset splits in (hu2020open). The links for validation and test are removed during the training stage and the links for validation are also not used in the test stage. All the models are trained till the loss converges and the models with the best validation performance is used to test.

Baselines. We choose 6 baselines: VGAE (kipf2016variational), P-GNN (you2019position), SEAL (zhang2018link), GNN Trans. (dwivedi2020generalization), LE (belkin2003laplacian) and Deepwalk (DW) (perozzi2014deepwalk). VGAE is a variational version of GAE (kipf2016variational) that utilizes GCN to encode both the structural information and node feature information, and then decode the node embeddings to reconstruct the graph adjacency matrix. SEAL is particularly designed for link prediction by using enclosing subgraph representations of target node-pairs. P-GNN randomly chooses some anchor nodes and aggregates only from these anchor nodes. GNN Trans. adopts LE as PE and merges LE into node features and utilizes attention mechanism to aggregate information from neighbor nodes. For VGAE, P-GNN and GNN Trans., the inner product of two node embeddings is adopted to represent links. LE and DW are two network embedding methods, where the obtained node embeddings are already positional features and directly used to predict links.

Implementation details. For VGAE, we consider six types of features: (1) node feature (N.): original feature of each node. (2) constant feature (C.): node degree. (3) positional feature (P.): PE extracted by Deepwalk. (4) one-hot feature (O.): one-hot encoding of node indices. (5) random feature (R.): random value (6) node feature and positional feature (N. + P.): concatenating the node feature and the positional feature. P-GNN uses node features and the distances from a node to some randomly selected anchor nodes as positional features (N. + P.). GNN Trans. utilizes node features and LE as positional features (N. + P.). SEAL adopt Double-Radius Node Labeling (DRNL) to compute deterministic distance features (N. + D.). For PEG, we consider node features plus positional features (N. + P.) or constant feature plus positional features (C. + P.).

Results are shown in Table 1 and Table 2. Over the small datasets in Table 1, VGAE with node features outperforms other features in Cora, Citeseer and Pubmed because the nodes features therein are mostly informative, while this is not true over the other three datasets. One-hot features and positional features almost achieve the same performance, which implies that that GNNs naively using PE makes positional features behave like one-hot features and may have instability issues. Constant features are not good because of the node ambiguity issues. Random features may introduce heavy noise that causes trouble in model convergence. Concatenating node features and positional features gives better performance than only using positional features but is sometimes worse than only using node features, which is again due to the instability issue by using positional features.

Although PGNN and GNN Trans. utilize positional features, they achieve subpar performance. SEAL outperforms all of the state-of-art methods, which again demonstrates that the effectiveness of distance features (li2020distance; zhang2020revisiting). PEG significantly outperforms all the baselines except SEAL. PEG+ by better using training sets achieves comparable or even better performance than SEAL, which demonstrates the contributions of the stable usage of PE. Moreover, PEG can achieve comparable performance in most cases even only paired with constant features, which benefits from the more expressive power given by PE (avoids node ambiguity). Note that PE without GNNs (LE or DW solo) does not perform well, which justifies the benefit by joining GNN with PE.

Regarding the OGB datasets, PGNN and GNN Trans. do not perform well either. Besides, PGNN cannot scale to large graphs such as collab. The results of DW and LE demonstrate that the original positional features may only provide crude information, so pairing them with GNNs is helpful. PEG achieves the best results on ddi, and performs competitively with SEAL on collab. The complexity of PEG is comparable to canonical GNNs. Note that we do not count the time of PE as it relates to the particular implementation. If PEG is used for online serving when the time complexity is more important, PE can be computed in prior. For a fair comparison, we also do not count the pre-processing time of SEAL, PGNN or GNN Trans.. Most importantly, PEG performs significantly faster than SEAL on test because SEAL needs to compute distance features for every link while PE in PEG is shared by links. Interestingly, DW seems better than LE as a PE technique for large networks.

Datasets & Baselines. Task 2 better evaluates the generalization capability of models. We consider 3 groups, including citation networks (coraciteseer and corapubmed) (sen2008collective), user-interaction networks (Twitch (EN)Twitch (RU) and Twitch (ES)Twitch (PT)) (rozemberczki2021multi) and biological networks (PPI) (hamilton2017inductive). For citation networks and user-interaction networks, we utilize 95%, 5% dataset splitting for training and validation over the training graph, and we use 10% existing links as test positive links in the test graph. For PPI dataset, we randomly select 3 graphs as training, validation and testing datasets and we sample 10% existing links in the validation/testing graphs as validation/test positive links.

Baselines & Implementation details. We use the same baselines as Task 1, while we do not use one-hot features for VGAE, since the training and test graphs have different sizes. As for node features, we randomly project them into the same dimension and then perform row normalization on them. Other settings are the same as Task 1. PE is applied to training and testing graphs separately while PE over testing graphs is computed after removing the testing links.

Results are shown in Table 3. Compared with Table 1, for VGAE, we notice that node features perform much worse (except PPI) than Task 1, which demonstrates the risks of using node features when the domain shifts. Positional features, which is not specified for the same graph, is possibly more generalizable over different graphs. Random features are generalizable while still hard to converge. PGNN and GNN Trans. do not utilize positional features appropriately and perform far from ideal. Both SEAL and PEG outperform other baselines significantly, which implies their good stability and generalization. PEG and SEAL again achieve comparable performance while PEG has much lower training and testing complexity. Our results successfully demonstrate the significance of using permutation equivariant and stable PE.

## 5 Conclusion

In this work, we studied how GNNs should work with PE in principle, and proposed the conditions that keep GNNs permutation equivariant and stable when PE is used to avoid the node ambiguity issue. We follow those conditions and propose the PEG layer. Extensive experiments on link prediction demonstrate the effectiveness of PEG. In the future, we plan to generalize the theory to more general PE techniques and test PEG over other graph learning tasks.

#### Acknowledgments

We greatly thank the actionable suggestions given by reviewers. H. Yin and P. L. are supported by the 2021 JPMorgan Faculty Award and the National Science Foundation (NSF) award HDR-2117997.

## Appendix A Proof of Lemma 3.4

Recall the eigenvalues of the PSD matrix are . Suppose one EVD of . In , is the eigenvector of so . Without loss of generality, we set .

Suppose . Now, we perturb by slightly perturbing and . We set

 u′k =√1−ϵ2uk+ϵuk+1 u′k+1 =−ϵuk+√1−ϵ2uk+1

Set for . Note that and . Then, the columns of still give a group of orthogonal bases.

Now we denote the above perturbation of as . Then, could be for any . Therefore, for sufficiently small ,

 minS′∈SN(p)∥PE(B+△B)S′−PE(B)∥2F = ∥[(√1−ϵ2−1)uk+ϵuk+1,(√1−ϵ2−1)uk+1−ϵuk]∥2F = ∥(√1−ϵ2−1)uk+ϵuk+1∥2+∥(√1−ϵ2−1)uk+1−ϵuk∥2 = 4(1−√1−ϵ2) = 2ϵ2+o(ϵ2). (8)

Next, we characterize .

 ∥△B∥2F=∥B+△B−B∥2F=∥N∑i=1λiu′iu′Ti−N∑i=1λiuiuTi∥2F = ∥λk(u′ku′Tk−ukuTk)+λk+1(u′k+1u′Tk+1−uk+1uTk+1)∥2F = ∥(λk+1−λk)[−ϵ2(ukuTk−uk+1uTk+1)+ϵ√1−ϵ2(ukuTk+1+uk+1uTk)]∥2F = (λk+1−λk)2(ϵ2∥ukuTk+1+uk+1uTk∥2F+o(ϵ2)) = 2(λk+1−λk)2(ϵ2+o(ϵ2)). (9)

Combining Eqs. 8,9, we have, for sufficiently small ,

 minS′∈SN(p)∥PE(B+△B)S′−PE(B)∥F>0.99|λk+1−λk|−1∥△B∥F+o(ϵ),

which concludes the proof.

## Appendix B Proof of Lemma 3.5

The result of the Lemma 3.5 can be derived from the Davis-Kahan theorem (davis1970rotation) and its variant (yu2015useful) that characterizes the eigenspace perturbation. We apply the Theorem 2 Eq.3 of (yu2015useful) to two PSD matrices.

###### Theorem B.1 (Theorem 2 (yu2015useful)).

Let two PSD matrices , with eigenvalues such that . For , let have orthonormal columns satisfying for . Then, there exists an orthogonal matrix such that

 ∥U(2)Q−U(1)∥F≤23/2min(p1/2∥B(1)−B(2)∥op,∥B(1)−B(2)∥F)λ(1)p+1−λ(1)p

By symmetry, use the above theorem again and we know there exists

 ∥U(1)Q′−U(2)∥F≤23/2min(p1/2∥B(1)−B(2)∥op,∥B(1)−B(2)∥F)λ(2)p+1−λ(2)p

Because , then there exists ,

 ∥U(2)Q−U(1)∥F≤23/2δmin(p1/2∥B(1)−B(2)∥op,∥B(1)−B(2)∥F) (10)

where .

When we apply a permutation matrix to permute the rows and columns of , then for any . Moreover, permuting the rows and columns of a PSD matrix will not change its eigenvalues. This means that can be replaced by in Eq.10 as long as is replaced by . Therefore,

 ∥PU(2)Q−U(1)∥F≤23/2δmin(p1/2∥B(1)−PB(2)PT∥op,∥B(1)−PB(2)PT∥F)

## Appendix C Proof of Theorem 3.6

To prove PE-equivariance, consider two graphs and that have perfect matching . So, , .

Let denote the Laplacian eigenmaps of , . Set , and and use Lemma 3.5. Because and , then there exists .

 Z(1)=P∗Z(2)Q (11)

Now, we consider a GNN layer that satisfies Eqs. 4,5. Also denote the output as and .

 (^X(1),^Z(1)) =g(A(1),X(1),Z(1)) (a)=g(P∗A(2)P∗T,P∗TX(2),P∗Z(2)Q) (b)=P∗g(A(2),X(2),Z(2)Q) (c)=(P∗^X(2),P∗^Z(2)Q)

Here (a) is because the perfect matching between


text:
### Course topics

• Complex numbers. Fields: definition and properties. Examples.
• Systems of Linear equations. Gauss elimination process.
• Matrices and operations on them. Invertible matrices.
• Determinant: definition and properties. Adjoint matrix. Cramer rule.
• Vector spaces and subspaces. Linear spanning and linear dependence. Basis and dimension. Coordinates with respect to a given basis.
• Linear transformations. Kernel and Image. Isomorphism of vector spaces. Matrix of a linear transformation with respect to given bases.
• The space of linear transformations between two vector spaces. Dual space

### Course Information

University course catalogue:
201.1.1211
Level:
First Year
Credits:
5.0

format: plain


text:
# A UV Complete Compositeness Scenario: LHC Constraints Meet The Lattice

We investigate a recently proposed UV-complete composite Higgs scenario in the light of the first LHC runs. The model is based on a $SU(4)$ gauge group with global flavour symmetry breaking $SU(5) \to SO(5)$, giving rise to pseudo Nambu-Goldstone bosons in addition to the Higgs doublet. This includes a real and a complex electroweak triplet with exotic electric charges. Including these, as well as constraints on other exotic states, we show that LHC measurements are not yet sensitive enough to significantly constrain the model's low energy constants. The Higgs potential is described by two parameters which are on the one hand constrained by the LHC measurement of the Higgs mass and Higgs decay channels and on the other hand can be computed from correlation functions in the UV-complete theory. Hence to exclude the model at least one constant needs to be determined and to validate the Higgs potential both constants need to be reproduced by the UV-theory. Due to its UV-formulation, a certain number of low energy constants can be computed from first principle numerical simulations of the theory formulated on a lattice, which can help in establishing the validity of this model. We assess the potential impact of lattice calculations for phenomenological studies, as a preliminary step towards Monte Carlo simulations.
Submitted 17 Mar 2017 to High Energy Physics - Phenomenology [hep-ph]
Published 20 Mar 2017
Updated 28 Aug 2017
Subjects: hep-ph hep-lat
Author comments: 12 pages, 6 figures
Report no: CP3-Origins-2017-008, DNRF90
http://arxiv.org/abs/1703.06064
http://arxiv.org/pdf/1703.06064.pdf
Scited by: David Mesterhazy


text:
An efficient peak finder for high coverage ChIP-seq experiments.

## Project description

The pique package is a high efficiency peak finder for ChIP-seq
experiments that yield high coverage allignments to the reference
genome. It was developed for studying gene expression in Halobacterium
salinarum sp. NRC1, sequenced using barcoded 40bp Illumina reads as
part of an ongoing project in Marc Facciotti's lab at UC Davis.

AUTHOR & CONTACT INFORMATION
----------------------------

Pique was written by Russell Neches, a graduate student in Jonathan
Eisen's laboratory.

Russell's Blog : http://vort.org/
Russell's Email : ryneches at ucdavis dot edu
Lab homepage : http://phylogenomics.wordpress.com/
Project Page : http://ryneches.github.com/pique/

INSTALLING
----------

General Instructions : You can do the usual python thing. We recommend using
virtualenv, because it's nice.

$cd ~$ virtualenv --system-site-packages opt
$PATH=~/opt/bin:$PATH
$pip install numpy # prerequisite$ pip install scipy # prerequisite
$pip install cython # prerequisite$ pip install pysam # prerequisite
$pip install argcomplete # suggested package$ pip install matplotlib # suggested package
$pip install ipython # suggested package$ pip install pique # install Pique
$pique test Debian and Ubuntu : We recommend using apt-get for most of the prerequisites.$ sudo apt-get install python-numpy \
python-scipy \
python-matplotlib \
python-virtualenv \
cython \
ipython
$cd ~$ virtualenv --system-site-packages opt
$PATH=~/opt/bin:$PATH
$pip install pysam$ pip install argcomplete
$pip install pique$ pique test

$cd ~$ cat >> .bashrc
PATH=~/opt/bin:$PATH export PATH [ctrl-D] MacOS : Unfortunately, MacOS doesn't come with virtualenv or any sort of useful global package management system. Here's how to fix that :$ sudo easy_install pip # install pip globally

Make sure pip works :

$pip Usage: pip COMMAND [OPTIONS] pip: error: You must give a command (use "pip help" to see a list of commands) Now, install virtualenv :$ sudo pip install virtualenv

Make sure that works :

$virtualenv You must provide a DEST_DIR ... Now, scroll back up and follow the General Instructions. Using argcomplete : If you installed argcomplete, you can enable tab completion for pique commands by placing this into your .bashrc : eval "$(register-python-argcomplete pique)"

TESTING DATA
------------

A testing data set is [available on
Figshare](http://figshare.com/articles/A_ChIP-seq_test_dataset/98106).
It was made from a his-tagged tfbD pulldown in _Halobacterium
salinarum_, sequenced on the Illumina GAII. The reads were mapped
using [bowtie](http://bowtie-bio.sourceforge.net/) to a cut-down
can be cited separately as :

A ChIP-seq test dataset. Russell Neches, Marc Facciotti, Elizabeth
G. Wilbanks, Phillip M. Seitzer. **figshare**.
Retrieved 06:12, Nov 27, 2012 (GMT)
http://dx.doi.org/10.6084/m9.figshare.98106

If you want to try out the test data, simply run :

$pique test The test data will automatically be downloaded to /tmp/pique/, and the resulting output data will be written to your current working directory. TESTS ----- Tests are designed to be used with nose. http://somethingaboutorange.com/mrl/projects/nose/ The tests (stupidly) depend on hard-coded paths to find the test data files, so you have to run nosetests from the main module directory (i.e., the one that has setup.py in it).$ cd pique
$nosetests DEPENDENCIES ------------ This package requires the following packages : scipy numpy pysam cython Suggested : matplotlib ipython samtools argcomplete Gaggle Genome Browser USAGE ----- This software can be used either as a stand-alone application, or as a library accessed by your own software. To use pique as a stand-alone application, there is a self-documenting command line interface :$ pique --help
usage: pique [-h] {batch,tk,test,bam2wav,mapmaker} ...

Pique, a ChIP-seq analytical tool.

optional arguments:
-h, --help show this help message and exit

commands:
{batch,tk,test,bam2wav,mapmaker}
batch command-line mode for peak detection
tk GUI mode for peak detection
bam2wav BAM to WAV conversion utility
mapmaker genome analysis region mapping utility

The application has four modes, batch, tk, test and mapmaker. To access
the GUI interface, run :

$pique tk The application window will appear. Enter a name for your project in the 'Project name' field; this will be the name prefix for the output files. Choose files for the IP and BG (background) tracks; these should be indexed BAM files, created by mapping your IP and control reads to the reference sequence. Many different tools can be used for this, such as bowtie, bwa and SHRiMP. The IP and background BAM files must contain identical contig names. If desired, choose a genome map file ('Map (optional)'). See below for how to create one. Enter the dominant fragment length of the sequencing library, and the read length used for the sequencing run. If you have performed quality trimming, you may wish to use the average or median read length after trimming for the read length. Then, click 'Run.' Your BAM files will be loaded and processed, and output files will be written in the directory from which pique.py was invoked. Run time for a bacterial genome depends on the number of mapped reads and the length of the genome. For our projects, we have found that a run takes about one to five minutes. BATCH MODE ---------- If you have many experiments to process, it may be more convenient to run pique from a script.$ pique batch -h
usage: pique batch [-h] -name NAME -ip IPFILE -bg BGFILE -map MAPFILE
[-a ALPHA] [-l L_THRESH] [-p]

optional arguments:
-h, --help show this help message and exit
-name NAME project name
-ip IPFILE BAM file for IP data
-bg BGFILE BAM file for control data
-map MAPFILE genome map file
-l L_THRESH expected binding footprint
-p make a pickel file

The arguments are essentially the same as those found in the GUI,
except for the option of making a pickle file. If this option is
enabled, after completing the anaysis, pique will dump the entire
analysis workbench object into a pickle file. This can be very useful
for debugging and data post-processing in Python. For example, the
pickle file can be used to load the analysis workbench into an
interactive ipython session and used to generate figures.

http://docs.python.org/2/library/pickle.html

MAPMAKER MODE
-------------

pique mapmaker -h usage: pique mapmaker [-h] -name NAME -bamfile BAMFILE [-window WINDOW] [-stride STRIDE] -highest HIGHEST -lowest LOWEST [-bins BINS] optional arguments: -h, --help show this help message and exit -name NAME project name -bamfile BAMFILE BAM file of aligned data -window WINDOW sliding window size -stride STRIDE stride length -highest HIGHEST highest histogram bin -lowest LOWEST lowest histogram bin -bins BINS number of histogram bins BAM2WAV MODE ------------ As an alternative to visualization, pique contains a utility for converting ChIP-seq data into audio data. The background alignment is subtracted from the IP alignment, and a separate WAV file is written for each contig. Coverage information for reads that map in the forward and reverse orientations is represented on the left and right audio channels, respectively. pique bam2wav -h
usage: pique bam2wav [-h] -name NAME -ip IPFILE -bg BGFILE

optional arguments:
-h, --help show this help message and exit
-name NAME project name
-ip IPFILE BAM file for IP data
-bg BGFILE BAM file for control data

GENOME MAP FILE
---------------

The Genome Map File is a GFF-formatted file describing three kinds of
features; analysis regions, masking regions, and normalization
regions. Analysis and masking region annotations are optional;
however, each analysis region MUST have at least one normalization
region. (Note : If you do not describe any analysis regions, one will
automatically be created spanning each contig. So, if you do not
describe any analysis regions for a contig, you must still describe at
least one normalization region for that contig.)

Analysis regions should use the feature name 'analysis_region' in the
file, and describe sub-regions of the contig that you wish to process
independently. For example, if there are inconsistencies in coverage
level due to gene dosage variations with respect to the reference,
processing the dosage regions separately can improve peak detection.

Masking regions should use the feature name 'mask' in the file, and
describe sub-regions of the analysis regions that you wish to delete
from the analysis. (Note: Masking regions *must* fall completely
within an analysis region.) This is useful for hiding coverage
aberrations due to repetitive regions, such as IS elements.

By default, an analysis region describing the whole contig is created
for each contig. When an analysis region is loaded by the user via the
mapping file, the default analysis region for that contig is deleted.

Normalization regions should use the name 'norm_region' in the map
file, and describe regions (within analysis regions) in which there
are thought to be no binding events. These regions will be used to
calibrate the sequencing coverage between the IP track and the control
track. If the user chooses poor normalization regions, Pique will
still function, but will produce incorrect normalization factors and
may set the peak detection cutoff too stringently.

Features described in the genome map file must use the same contig
names as the IP and background BAM files. To see them, run :

\$ samtools view -H BAMfile.bam

Most columns in the GFF file are unused, and may be left empty (as
long as the correct number of tabs are present). The required fields
are :

0 contig name
3 start coordinate
4 end coordinate

An example genome map file is provided (data/map.gff).

OUTPUT FILES
------------

<name>.IP.track : A GGB-formatted track file of the IP data
<name>.BG.track : A GGB-formatted track file of the BG data
<name>.bookmark : A list of GGB bookmarks for each peak
<name>.qp : GGB-formatted quantitative positional data
of binding coordinates
<name>.gff : A GFF file of each peak
<name>.peak.tsv : Peak statistical quantities in TSV format

The GFF output file includes the following columns :

0 contig name
1 software version
2 feature description
3 start coordinate
4 end coordinate
5 enrichment ratio relative to background

The TSV output includes the following columns :

0 contig
1 start
2 stop
3 binds_at # binding coordinate
4 enrichment_ratio
5 average_contig_norm # mean of all norms
6 std_contig_norm # standard deviation of all norms
7.. # all subsequent colunms are the norms

the required GGB bookmark information :

binds_at estimated binding coordinate
enrichment_ratio enrichment ratio relative to background
norm_0, norm_1... the normalization factors calculated from the
normilization regions

CAVEATS
-------

Binding coordinates : The peak calling step (pique.py) will attempt to
calculate a binding coordinate for the putative peaks it finds. The
method used is extremely naive, but we find that it generally comes
within about 5bp of the expected binding site.

Double peaks : Some enriched regions contain two binding sites, but
the algorithm is unable to de-convolute them. We have tried running
these regions through several other peak callers with little success.
We have included a script for identifying sites that are likely to be
double peaks to assist with curation.

DOWNSTREAM ANALYSIS
-------------------

Pique does not attempt to filter peaks that are statistically
insignificant. We have found that this part of the analysis is rather
specific to the data and to the experiment.

To address this, Pique is designed to achieve a low false-negative
rate at the cost of a potentially high false-positive rate (it appears
that the false-positive rate is in practice rather low compared to
other software, but we have not implemented any filtering to prevent
them from happening). The idea is that it is painstaking work to find
a putative peak, it is less difficult to discard unsatisfactory peaks
once they have been found. Thus, some kind of post-filtering is
necessary. Pique provides the user with output that can be used to
support a variety of such statistical tests.

Some recommended filtering might include :

[1] Eliminate peaks that are significantly narrower than the size
range of the sequencing library, and perhaps other peaks that
cluster with them.

[2] Eliminate peaks with a normalized enrichment ratio below 1.0,
or peaks that cluster with them.

[3] Eliminate peaks that have predicted binding sites that are
very skewed from the center of the enriched region.

Depending on how many peaks are recovered, the user may wish to try
one or all of these, perhaps with clustering to avoid arbitrary
cutoffs.

However, we do not recommend trying to generate a "perfect" peak list
by statistical analysis alone.

MANUAL CURATION
---------------

Microbial genomes are fairly small. It is probably not worth the
effort to undertake a very complicated statistical effort to eliminate
all false positives. We recommend applying a few basic statistical
into the Gaggle Genome Browser.

Once the data is loaded into the browser, view the bookmark list. When
you select a bookmark, the browser will automatically scan to that
region of the genome and highlight the putative peak region. If you
think the peak is a false positive, press the delete key.

When you are finished, save a copy of the bookmark file. We find that
curation of a microbial genome in this way takes about ten to twenty
minutes.

INSPIRATIONAL QUOTE
-------------------

I met men at every turn who owned from one thousand to thirty thousand
"feet" in undeveloped silver mines, every single foot of which they
believed would shortly be worth from fifty to a thousand dollars—and
as often as any other way they were men who had not twenty-five
dollars in the world. Every man you met had his new mine to boast of,
and his "specimens" ready; and if the opportunity offered, he would
infallibly back you into a corner and offer as a favor to you, not to
him, to part with just a few feet in the "Golden Age," or the "Sarah
Jane," or some other unknown stack of croppings, for money enough to
get a "square meal" with, as the phrase went. And you were never to
reveal that he had made you the offer at such a ruinous price, for it
was only out of friendship for you that he was willing to make the
sacrifice. Then he would fish a piece of rock out of his pocket, and
after looking mysteriously around as if he feared he might be waylaid
and robbed if caught with such wealth in his possession, he would dab
the rock against his tongue, clap an eyeglass to it, and exclaim:

"Look at that! Right there in that red dirt! See it? See the specks of
gold? And the streak of silver? That's from the Uncle Abe. There's a
hundred thousand tons like that in sight! Right in sight, mind you!
And when we get down on it and the ledge comes in solid, it will be
the richest thing in the world! Look at the assay! I don't want you to
believe me—look at the assay!"

Then he would get out a greasy sheet of paper which showed that the
portion of rock assayed had given evidence of containing silver and
gold in the proportion of so many hundreds or thousands of dollars to
the ton.

I little knew, then, that the custom was to hunt out the richest piece
of rock and get it assayed! Very often, that piece, the size of a
filbert, was the only fragment in a ton that had a particle of metal
in it—and yet the assay made it pretend to represent the average value
of the ton of rubbish it came from!

- Mark Twain, Roughing It

LEGAL STUFF
-----------

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

* Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.

* Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in
the documentation and/or other materials provided with the
distribution.

* Neither the name of the University of California, Davis nor the
names of its contributors may be used to endorse or promote
products derived from this software without specific prior
written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

## Project details

Uploaded source


text:
# Lessons from teaching gifted elementary school students (Part 1)

Every so often, I’ll informally teach a class of gifted elementary-school students. I greatly enjoy interacting with them, and I especially enjoy the questions they pose. Often these children pose questions that no one else will think about, and answering these questions requires a surprisingly depth of mathematical knowledge.

Here’s a question I once received:

When playing with my calculator, I noticed the following pattern:

$256 \times 256 = 65,5\underline{36}$

$257 \times 257 = 66,0\underline{49}$

$258 \times 258 = 66,5\underline{64}$

Is there a reason why the last two digits are perfect squares? I know it usually doesn’t work out this way.

I leave a thought bubble in case you’d like to think this. One way of answering this question appears after the bubble.

The answer is: This always happens as long as the tens digits is either 0 or 5.

To see why, let’s expand $(50n + k)^2$, where $n$ and $k$ are nonnegative integers and $0 \le k \le 9$. If $n$ is odd, then the tens digit of $50n+k$ will be a 5. But if $n$ is even, then the tens digit of $50n+k$ will be 0.

Whether $n$ is even or odd, we get

$(50n+k)^2 = 2500n^2 + 100nk + k^2 = 100(25n^2 + nk) + k^2$

The expression inside the parentheses is not important; what is important is that $100(25n^2 + nk)$ is a multiple of 100. Therefore, the contribution of this term to the last two digits of $(50n+k)^2$ is zero. We conclude that the last two digits of $(50n+k)^2$ is just $k^2$.

Naturally, elementary-school students are typically not ready for this level of abstraction. That’s what I love about this question: this is a completely natural question for a curious grade-school child to ask, but the teacher has to have a significantly deeper understanding of mathematics to understand the answer.

Previous Post


text:
1. Jul 18, 2005

### Townsend

Last edited by a moderator: Apr 21, 2017
2. Jul 18, 2005

### Knavish

Wow.. Really aggravating. Does anybody else agree there should be more intellectually demanding requirements to become a police officer?

3. Jul 18, 2005

### Townsend

I do...I agree with you 100 percent. I can't agree any more than that.

(edit) but I also think it is up to the state to determine what the the requirements should be.

Last edited: Jul 18, 2005
4. Jul 18, 2005

I dont get it.. whats the 'charge'? She didnt steal anything from him. He willfully gave her the money, whatever the amount, accepted the goods and services for it, and left. As far as the law is concerned he exchanged money for goods/services. It shouldnt matter if he paid her 50 or 100 and it was only a $10 order. Rest are tips, no? 5. Jul 18, 2005 ### Townsend I have no idea, this guy is a control freak...he needs to be treated like that, completely helpless to defend yourself from abusive authority. Grrrrr..... Then the fact that he shoots mace in her face!!!!!!!!!!!!!!!!!!!!!!!!!!! 6. Jul 19, 2005 ### Pengwuino hahahahahaha give that cop a medal. I think there shoudl be higher intellectual standards for working at a mcdonalds! Like we all havent made a mistake like that before and wanted to go nuts. What the hell is so hard about walken out to a police car. If your innocent, your innocent and there will be tapes to prove it but nooooo, you gotta act like a little kid and you end up getting spanked. This must have been in california. Where else can you act like a moron and get$60,000

7. Jul 19, 2005

### Archon

You really believe that the cop was justified in arresting her
a)over 10 dollars
b)for a "crime" she didn't commit

As for the money: she had to go to the hospital, and the cop was certainly taking his job too far, so SOME money was probably justified (at least hospital bills). Probably not $60 000, though. 8. Jul 19, 2005 ### Townsend I agree except I think it should have been him paying her out of his pocket. There was no crime and it was his mistake. Even if she had given him the wrong change, he does not have the authority to arrest her for that. Not to mention the fact the he should have called in backup since it is a conflict of interest. Dayton Ohio is one place I will make sure to avoid. Regards, 9. Jul 19, 2005 ### Kazza_765 I remember a case here where a man applying to join the police force was rejected because he scored too HIGH on an IQ test. They said that he would be better suited looking for employment elsewhere. 10. Jul 19, 2005 ### Pengwuino a) petty theft, very much an arrestable offense b) your telling me police should be sued everytime they bring in someone who ends up being innocent? Think about that one... The cop asks her to come with him and she refuses and starts crying saying her moms coming when she could have just walked away with him, end up getting the security tapes and the manager's word and boom, back to work, no spray no harm no foul I mean if i walked up to you on the street and stole a$20 out of your pocket and you flag down a cop, would you be satisfied if he asked me if i had your $20 and i simply said no and that was it, case closed? 11. Jul 19, 2005 ### Knavish It doesn't matter. The way he "arrested" her was in a sick, domineering manner. Moreover, he had NO evidence that she "stole" anything; he simply started accusing her. *I just read the last part of your post.. The thing here is, she even asked, begged for him to search her. And he didn't. That said, if it were me, I would have just allowed him to arrest me, and kicked some ass later. Last edited: Jul 19, 2005 12. Jul 19, 2005 ### Pengwuino She acted like an idiot, she had it coming. The police arent around to just allow you to pull your temper tantrum and THEN politely arrest you. And most cases of petty theft dont have much evidence when it comes to money but you still arrest and look for evidence. An arrest is not a conviction, remember that. She could have shut up, got into the police car, drive to the station, review hte tapes, walked out, its that simple. We live in a society and in return for having a government, we do need to realize we may have to give up a few hours of our time once in a while And who knows, he may not have been allowed to search her. I know in some states if you want to search someone of the opposite sex, you have to call for another officer of that same sex to do the search. 13. Jul 19, 2005 ### Danger Getting sprayed and having to go to the hospital might have been to her advantage. He seems like the kind of guy who would have driven her out to the woods and raped her if she'd gone willingly. Also notice that he had the spray out and ready to use as soon as she started to protest her innocence. Even a known gang member with a criminal history would have received better treatment than that by a civilized cop, never mind an innocent minor trying to work an honest job. He should have been fired from the force and arrested for assault. 14. Jul 19, 2005 ### Pengwuino haha, known gang member around here gets slammed up against walls after they get chased down. 15. Jul 19, 2005 ### Kazza_765 One of my bosses ran from the cops when he was younger after a fight outside a pub. Some of his friends started yelling "shoot him, shoot him" but he didn't know it was his friends so he panicked, stopped running and put his hands in the air and waited. When the cops caught up he was spear tackled and beaten by two cops. Had to go to hospital with broken shoulder and broken arm. I've seen a guy dragged out of the footy because he was drunk. Five cops threw him to the ground and started shouting at him. He was yelling "I just want to go home" and started crying. He wasn't resisting at all. Two cops jumped on top of him, one was kneeling on his head, another was hitting him, the others were screaming at him. All the while he was just lying there crying. In the end they didn't even arrest him, they just let him get up and go. I ended up giving the poor guy my number and filing a report at the local cop shop but I don't think anything ever came of it (surprise, surprise). edit: typo 16. Jul 19, 2005 ### Pengwuino haha shoot him shoot him. I woulda pissed my pants if i heard that. And what the hecks a "cop shop". Do you buy cops there? 17. Jul 19, 2005 ### Kazza_765 hah, just slang for a police station. 18. Jul 19, 2005 ### devil-fire iv watched the show "cops" and it made me feel sick because nowhere else in all of society, outside of nation defence can people Ignore human rights and get as little punishment. maybe its "part of the job they have to be tough on people" well thats what the reasoning was behind letting police trian attack dogs on Live, Unprotected people in africa. it really bugs me when this stuff happens but it bugs me more when people arnt punished for it. if there was no wrong doing why would she be getting 60,000? the police officers in charge of officialy repremanding that cop used Taxpayer's money to get their friend out of trouble! yes. she would not have got sprayed if she just went out to the police car but does that mean she should have gone to the car? no. she wasnt being charged with anything, it was just some guy telling her to get off work so he can do whatever he wants to do. 19. Jul 20, 2005 ### Pengwuino Well devil, what other job outside of national defense are you running the risk of getting killed because a kid doesnt want to pay a$80 parking ticket. And your also really forgetting that stepping into a cops car does not necessarily mean your going to jail. It can either mean "sit here and shut up for a second while i look at something" or "hey we're bringing you down for questioning where you can plead your case".

The police have the right to pretty much say "go to my car while i do whatever i want", and we all agree to that every day we decide to live in society. If you dont like those rules, you can live in a cave. There are rules in place so that it doesnt get out of hand but 1 or 2 times does not cut it as some sort of joke of a human rights abuse.

20. Jul 20, 2005

### Kazza_765

I agree with that and I think its ridiculous when cops are persecuted for "unnecessarily" injuring or shooting someone that was armed and obviously unstable or threatening them. But this girl was clearly not a threat. He could have waited for her mama to get there, he could have gone and spoken to the manager or he could have just stood there and waited for her to calm down enough to converse rationally. There was no urgency to the situation that would require him to assault her.

21. Jul 20, 2005

Police-issued lawful orders

I am not a lawyer. The following comments are my personal opinions.

All persons within the jurisdiction of the United States are required to do anything any sworn peace officer tells them to do at any time. A person does not have to be charged with something in order for a police officer to be able to issue a lawful order, and for the person so ordered to be legally-compelled to obey. For example, if, in a given instance, a peace officer orders you to step two feet to your right, and you do not promptly do it, you could be prosecuted for a crime and be ordered to pay a fine and/or to serve time in a county jail or a state or federal prison.

22. Jul 20, 2005

### Pengwuino

But she was uncooperative. My opinion is that the police should not sit around and wait for people to pull their temper tantrums. Also, it was highly unlikely her "mom" was going to be comen aroudn anytime soon. She was just cryen because she's immature. I mean hell, most parents dont put up with their 6 year old kids temper tantrums... so i dont think the police should put up with grown/young adults temper tantrums

23. Jul 20, 2005

### cronxeh

what the hell are you smoking

Edit: no, seriously, I had to re-read this at least 5 times for it to sink in..

Last edited: Jul 20, 2005
24. Jul 20, 2005

### Ivan Seeking

Staff Emeritus
We have a few cops in the family and as a result I have never trusted the police less than I do now.

Many years ago my dad's best buddy changed professions and joined the LAPD. Within a year or two of working the worst slums in LA, this guy [Mike] was a changed person. He became mean, abusive, arrogant, a racist, and no one including his own family or my dad could stand to be around him any longer. He eventually left the force to save his marriage.

A great-uncle [by marriage], a career cop in LA, died a few years ago. I got some of the illegal weapons that he carried throughout his career. And talk about a racist! :surprised

My cousin who comes from a family of cops, married a cop. Even she can't stand to listen to the stories of what goes on.

My brother-in-law is a cop. Although he seems to be a fairly decent guy, his mentality is downright scary.... and dumb as a rock.

25. Jul 20, 2005

--
Results 1 - 20 of about 3,810 for "failure to obey a lawful order". (0.05 seconds)
--

http://www.ci.loveland.co.us/finance/municipalcode/Title_09/Chap%209.04.htm [Broken]

--
Section 9.04.030 - Failure to obey a lawful order of a police officer

It is unlawful for any person to fail to obey the lawful order of a police officer. A lawful order is that order issued by a police officer in the exercise of his assigned duties relating to the enforcement of the penal law or the preservation of the peace or the protection of the safety of a person. A police officer may issue a lawful order while performing his assigned duties or preserving the peace or protecting the safety of a person when in uniform, or, if not in uniform, after having identified himself as a police officer. (Ord. 3221 § 1, 1985)
--

Last edited by a moderator: May 2, 2017


text:
# The connection between integration and area

#### Poirot

##### Banned
My understanding is that (definite) integration defines area in R^2, volume in R^3 etc, and my question is: would calculating an area in R^2 using integration give the same answer as counting the unit squares. If so, how did they ensure to define integration in such a way as to give the same result as most people's definition?

#### tkhunny

##### Well-known member
MHB Math Helper
If you are thinking "Unit Squares", you are not getting the idea of integration. They used to think this way in Ancient Greece - vaguely, if we can just quantize it, we'll find the fundamental unit. This is not good enough. The area of each "piece" really is zero!

We can get most peoples' definition to match up by teaching them THE definition. There are other definitions for integration - to handle discontinuities and various other things.

Last edited:

#### CaptainBlack

##### Well-known member
My understanding is that (definite) integration defines area in R^2, volume in R^3 etc, and my question is: would calculating an area in R^2 using integration give the same answer as counting the unit squares. If so, how did they ensure to define integration in such a way as to give the same result as most people's definition?
The Riemann integral is set up to be the limit if it exists of the area of sets rectangles of finite width that approximate the region under the curve as the widths tend to zero. So it is to a hand-waving approximation the result of counting squares as the size of the grid goes to zero.

It is silly to ask how did they ensure this result, the definition of the integral is set up explicity to match the intuitive idea of area in those cases where the intuitive notion makes sense.

CB

#### Poirot

##### Banned
Thanks for the responses


text:
# Flip operator's equality to Double Fourier

## Main Question or Discussion Point

Some authors say that applying Fourier transform twice flips the vector, F2[x(t)] = x(-t). Yet, the simple checks proves this wrong. For instance, take 2x2 DFT:

$$\left[\begin{array}{cc}1&1\\ 1&-1\end{array}\right]^2 = \left[\begin{array}{cc}1&0\\ 0&1\end{array}\right]$$

The Identity is different from counter-identity. It cannot therefore flip the vector elements. Where is the mistake?


text:
This site is supported by donations to The OEIS Foundation.

# User:Daniel Suteu

Open-source software developer and independent researcher, with main interests in programming languages, mathematics (number theory), poetry and science.

In March 2013, I started the Sidef programming language project, which combines many good things from good languages, trying to make programming easier and more enjoyable, focusing primarily on simplicity, elegance and readability.

Among other things, the language comes with fast built-in methods for primality testing and prime factorization, along with many other number-theoretic functions, most of them provided by Dana Jacobsen's excellent Math::Prime::Util::GMP module. Also built-in, we have support for arbitrary large integers, rationals, floats and complex numbers, using the GMP, MPFR and MPC libraries.

The language can be tried online at: https://tio.run/#sidef.

WWW:

## Partial sums of arithmetical functions

For any arithmetical function ${\displaystyle f(k)}$, we have the following identity for m>=0:

${\displaystyle \sum _{k=1}^{n}\sum _{d|k}f(d)*(k/d)^{m}=\sum _{k=1}^{n}\sum _{d|k}f(k/d)*d^{m}=\sum _{k=1}^{n}f(k)*F_{m}(\left\lfloor n/k\right\rfloor )}$

where ${\displaystyle F_{n}(x)}$ are the Faulhaber polynomials, defined as:

${\displaystyle F_{n}(x)={\frac {B_{n+1}(x+1)-B_{n+1}(1)}{n+1}}}$

where ${\displaystyle B_{n}(x)}$ are the Bernoulli polynomials. The Faulhaber polynomials are particularly useful in efficiently summing the m-th powers, with m >= 0, of the first n positive integers:

${\displaystyle \sum _{k=1}^{n}k^{m}=F_{m}(n)}$

We're interested in computing the following sum efficiently, for m>=0:

${\displaystyle R_{m}(n)=\sum _{k=1}^{n}f(k)*F_{m}(\left\lfloor n/k\right\rfloor )}$

If the partial sums of ${\displaystyle f(k)}$ can be computed efficiently, then we can create a sub-linear time algorithm for computing ${\displaystyle R_{m}(n)}$.

${\displaystyle S(n)=\sum _{k=1}^{n}f(k)}$

which gives us the following sub-linear time formula, assuming that ${\displaystyle S(n)}$ can be computed efficiently:

${\displaystyle R_{m}(n)=\sum _{k=1}^{\left\lfloor {\sqrt {n}}\right\rfloor }F_{m}(k)*(S(\left\lfloor n/k\right\rfloor )-S(\left\lfloor n/(k+1)\right\rfloor ))+\sum _{k=1}^{\left\lfloor n/(\left\lfloor {\sqrt {n}}\right\rfloor +1)\right\rfloor }f(k)*F_{m}(\left\lfloor n/k\right\rfloor )}$

Read more on this at: https://trizenx.blogspot.com/2018/11/partial-sums-of-arithmetical-functions.html

## Partial sums of the sigma function

For m >= 0 and j >= 0, we have:

${\displaystyle \sum _{k=1}^{n}k^{m}\sigma _{j}(k)=\sum _{k=1}^{n}k^{m+j}*F_{m}(\left\lfloor n/k\right\rfloor )=\sum _{k=1}^{n}k^{m}*F_{m+j}(\left\lfloor n/k\right\rfloor )}$

where ${\displaystyle F_{n}(x)}$ are the Faulhaber polynomials.

An asymptotic approximation to this partial sum, with m >= 0 and j >= 1, is given by the following formula:

${\displaystyle \sum _{k=1}^{n}k^{m}\sigma _{j}(k)\sim {\frac {\zeta (j+1)n^{j+m+1}}{j+m+1}}}$

where ${\displaystyle \zeta (s)}$ is the Riemann zeta function.

## Partial sums of the Jordan totient function

The Jordan totient function is a generalization of the Euler's totient function, and is defined as:

${\displaystyle J_{m}(n)=n^{m}\prod _{p|n}(1-1/p^{m})}$

and is multiplicative with:

${\displaystyle J_{m}(p^{k})=p^{km}-p^{(k-1)m}}$

An elegant formula for computing partial sums of the Jordan totient function, is given in terms of the Möbius function and the Faulhaber polynomials:

${\displaystyle \sum _{k=1}^{n}J_{m}(k)=\sum _{k=1}^{n}\mu (k)*F_{m}(\left\lfloor n/k\right\rfloor )}$

An asymptotic approximation to this partial sum, with m >= 1, is given as:

${\displaystyle \sum _{k=1}^{n}J_{m}(k)\sim {\frac {n^{m+1}}{(m+1)\zeta (m+1)}}}$

where ${\displaystyle \zeta (s)}$ is the Riemann zeta function.

## Partial sums of the Dedekind psi function

The generalized Dedekind psi function can be defined in terms of the Jordan totient function, as:

${\displaystyle \psi _{m}(n)={\frac {J_{2m}(n)}{J_{m}(n)}}}$

and is multiplicative with:

${\displaystyle \psi _{m}(p^{k})=p^{km}+p^{(k-1)m}}$

Partial sums of the Dedekind psi function can be expressed in terms of the absolute value of the Möbius function and the Faulhaber polynomials:

${\displaystyle \sum _{k=1}^{n}\psi _{m}(k)=\sum _{k=1}^{n}|\mu (k)|*F_{m}(\left\lfloor n/k\right\rfloor )}$

with the following asymptotic approximation for m >= 1:

${\displaystyle \sum _{k=1}^{n}\psi _{m}(k)\sim {\frac {n^{m+1}\zeta (m+1)}{(m+1)\zeta (2(m+1))}}}$

where ${\displaystyle \zeta (s)}$ is the Riemann zeta function.

## Partial sums of the omega(n) and bigomega(n) functions

We define the generalized ${\displaystyle \omega _{m}(n)}$ and ${\displaystyle \Omega _{m}(n)}$ functions as:

${\displaystyle \omega _{m}(n)=\sum _{p^{k}|n}{\frac {n^{m}}{p^{m}}}}$

${\displaystyle \Omega _{m}(n)=\sum _{p^{k}|n}\sum _{j=1}^{k}{\frac {n^{m}}{p^{jm}}}}$

where ${\displaystyle p^{k}}$ are primes ${\displaystyle p}$ dividing ${\displaystyle n}$, with multiplicity ${\displaystyle k}$.

For ${\displaystyle \omega _{m}(n)}$ we have the following sequences:

${\displaystyle \omega _{0}(n)=}$ A001221(n)

${\displaystyle \omega _{1}(n)=}$ A069359(n)

${\displaystyle \omega _{2}(n)=}$ A322078(n)

Similarly, for ${\displaystyle \Omega _{m}(n)}$, we have:

${\displaystyle \Omega _{0}(n)=}$ A001222(n)

${\displaystyle \Omega _{1}(n)=}$ A095112(n)

${\displaystyle \Omega _{2}(n)=}$ A322664(n)

Partial sums of this functions can be expressed in terms of the Faulhaber polynomials, as:

${\displaystyle \sum _{k=1}^{n}\omega _{m}(k)=\sum _{p}^{n}F_{m}(\left\lfloor n/p\right\rfloor )}$

${\displaystyle \sum _{k=1}^{n}\Omega _{m}(k)=\sum _{p^{k}}^{n}F_{m}(\left\lfloor n/p^{k}\right\rfloor )}$

where ${\displaystyle p}$ and ${\displaystyle p^{k}}$ (with k>=1) run over the prime numbers and the prime powers, respectively, less than or equal to ${\displaystyle n}$.

For m>=1, the partial sums of ${\displaystyle \omega _{m}(k)}$ can be described asymptotically as:

${\displaystyle \sum _{k=1}^{n}\omega _{m}(k)\sim F_{m}(n)*P(m+1)}$

where ${\displaystyle F_{m}(n)}$ are the Faulhaber polynomials and ${\displaystyle P(s)}$ is the Prime zeta function, defined as:

${\displaystyle P(s)=\sum _{p}{\frac {1}{p^{s}}}}$

Very similarly, for m>=1, the partial sums of ${\displaystyle \Omega _{m}(k)}$ satisfy:

${\displaystyle \sum _{k=1}^{n}\Omega _{m}(k)\sim F_{m}(n)*Q(m+1)}$

where ${\displaystyle F_{m}(n)}$ are the Faulhaber polynomials and ${\displaystyle Q(s)}$ is defined as:

${\displaystyle Q(s)=\sum _{k=1}^{\infty }\sum _{p}{\frac {1}{p^{sk}}}=\sum _{p}{\frac {1}{p^{s}-1}}}$

where ${\displaystyle p}$ runs over the prime numbers.

## Partial sums - OEIS sequences

Considering the following partial sum, where ${\displaystyle f(k)}$ is an arithmetic function and ${\displaystyle F_{n}(x)}$ are the Faulhaber polynomials:

${\displaystyle R_{m}(n)=\sum _{k=1}^{n}f(k)*F_{m}(\left\lfloor n/k\right\rfloor )}$

gives us the following table of interesting sequences:

+------------+------------+------------+
|    f(k)    |   R_0(n)   |   R_1(n)   |
+------------+------------+------------+
| A000012(k) | A006218(n) | A024916(n) |
| A000027(k) | A024916(n) | A143127(n) |
| A010051(k) | A013939(n) | A322068(n) |
| A008966(k) | A064608(n) | A173290(n) |
| A008683(k) | A000012(n) | A002088(n) |
| A000290(k) | A064602(n) | A143128(n) |
| A000010(k) | A000217(n) | A272718(n) |
| A007434(k) | A000330(n) |            |
| A069513(k) | A022559(n) |            |
| A034444(k) | A061503(n) |            |
+------------+------------+------------+

## Generalized Pillai arithmetical function

For any arithmetic function ${\displaystyle f(k)}$, we have the following identity:

${\displaystyle \sum _{k=1}^{n}f(gcd(n,k))=\sum _{d|n}f(d)*\phi (n/d)}$

where ${\displaystyle \phi (x)}$ is the Euler totient function.


text:
# How can gravity affect light?

I understand that a black hole bends the fabric of space time to a point that no object can escape.

I understand that light travels in a straight line along spacetime unless distorted by gravity. If spacetime is being curved by gravity then light should follow that bend in spacetime.

In Newton's Law of Universal Gravitation, the mass of both objects must be entered, but photon has no mass, why should a massless photon be affected by gravity in by Newton's equations? What am I missing?

Newton's law does predict the bending of light. However it predicts a value that is a factor of two smaller than actually observed.

The Newtonian equation for gravity produces a force:

$$F = \frac{GMm}{r^2}$$

so the acceleration of the smaller mass, $m$, is:

$$a = \frac{F}{m} = \frac{GM}{r^2}\frac{m}{m}$$

If the particle is massless then $m/m = 0/0$ and this is undefined, however if we take the limit of $m \rightarrow 0$ it's clear that the acceleration for a massless object is just the usual $a = GM/r^2$. That implies a photon will be deflected by Newtonian gravity, and you can use this result to calculate the deflection due to a massive object with the result:

$$\theta_{Newton} = \frac{2GM}{c^2r}$$

The calculation is described in detail in this paper. The relativistic calculation gives:

$$\theta_{GR} = \frac{4GM}{c^2r}$$

The point of Eddington's 1919 expedition was not to show that light was bent when no bending was expected, but rather to show that the bending was twice as great as expected.

• A downvote? Why was that? I didn't think I'd said anything controversial. If you'd like to say why you downvoted I'll have a look at editing my answer accordingly. Aug 12, 2014 at 14:06
• Perfect! Thank you! I was reasonably certain that was the answer. I appreciate your help. Aug 12, 2014 at 16:56
• Well... If a particle has zero mass then F is zero and you can't really use newtonian mechanics to begin with. (Im not the one who downvoted, just think that might be the complain) Jul 17, 2017 at 18:32
• What John's answer left out is that when you take limit as m goes to zero, you have to apply L'Hopital's rule, which should come out to 1. Thus, F is not zero. Jan 13, 2019 at 2:47
• No, the force would still be zero (without relativity) if m is zero. The LHopitals rule only applies to the acceleration. So I’m confused as well..if F is zero for a massless particle then what’s causing the acceleration? This leads me to question if this could really be explained purely classically to within a factor of 2. Feb 25, 2019 at 9:56

One can in principle consider a Schwarzschild spacetime:

$ds^2 = -\left(1- \frac{2M}{r}\right)dt^2 + \frac{dr^2}{1- \frac{2M}{r}} + r^2 \left(d\theta^2 + \sin^2 \theta d \phi^2\right)$

The Lagrangian of geodesics is then given by:

$\mathcal{L} = \frac{1}{2} \left[- \left(1 - \frac{2M}{r}\right)\dot{t}^2 + \frac{\dot{r}^2}{1-\frac{2M}{r}} + r^2 \dot{\theta}^2 + r^2 \sin^2 \theta \dot{\phi}^2\right]$

After applying the Euler-Lagrange equations, and exploiting the fact that the S-metric is spherically symmetric and static, one obtains the orbital equation for light as (After defining $u = 1/r$) as:

$\frac{d^2 u}{d\phi^2} + u = 3 M u^2$.

It 's pretty difficult to solve this ODE. In fact, I don't think a closed-form solution exists. One can apply a perturbation approach. Defining an impact parameter $b$, one can obtain an ansatz solution to this ODE as:

$u = \frac{1}{b} \left[\cos \phi + \frac{M}{b} \left(1 + \sin^2 \phi\right)\right]$.

One can derive the following relationship:

$u\left(\frac{\pi}{2} + \frac{\delta \phi}{2}\right) = 0$,

where $\delta \phi$ is the deflection angle.

Now, finally Taylor expanding $u$ above around $\pi/2$, one can show that, in fact:

$\delta \phi = \frac{4M}{b}$,

which is the required result.

In this answer we derive the formula for the angle of deflection

$$\theta ~=~\frac{2GM}{b}\left(\frac{1}{v_0^2} + \frac{1}{c^2}\right) +{\cal O}(M^2) \tag{1}$$

of a (massive or massless) particle in a Schwarzschild spacetime. Here $$b$$ is the impact parameter and $$v_0$$ is the asymptotic speed (which for a massless particle is $$c$$). The Newtonian limit is $$c\to \infty$$.

Sketched proof:

1. By spherical symmetry, we can take the orbit plane = equatorial plane: $$\theta=\frac{\pi}{2}$$. We start from the geodesic equations \hspace{-5em}\begin{align} E~=~&n^{-1}\frac{dt}{d\lambda} , \cr n^{-1} ~:=~&1 - \frac{r_s}{r}, \cr r_s~:=~&\frac{2GM}{c^2}, \end{align}\tag{5.61/7.43/6.3.12} $$\hspace{-5em} L~=~r^2\frac{d\phi}{d\lambda}, \tag{5.62/7.44/6.3.13}$$ \hspace{-5em}\begin{align} \epsilon c^2~=~&n^{-1}c^2 \left(\frac{dt}{d\lambda}\right)^2 \cr ~-~&n\left(\frac{dr}{d\lambda}\right)^2 -r^2\left(\frac{d\phi}{d\lambda}\right)^2, \end{align}\tag{5.55/7.39/6.3.10} cf. Refs. 1-3. Here $$[\lambda]=\text{Time}, \qquad [E] ~=~\text{dimensionless}, \qquad [L] ~=~\frac{\text{Length}^2}{\text{Time}}. \tag{2}$$

• Massive particle: $$\epsilon=1$$ and $$\lambda=\tau$$ proper time.

• Massless particle: $$\epsilon=0$$ and $$\lambda$$ not proper time.

This leads to \hspace{-5em} \begin{align} \underbrace{ (cE)^2 }_{\text{"energy"}} ~=~& \underbrace{ \left(\frac{dr}{d\lambda}\right)^2 }_{\text{"kinetic energy"}}\cr ~+~& \underbrace{n^{-1}\left(\frac{L^2}{r^2}+\epsilon c^2 \right) }_{\text{"effective potential energy"}}. \end{align}\tag{5.64/7.46/6.3.14} The reader may ponder whether the $$\epsilon$$ parameter leads to a discontinuity in the angle $$\theta$$ of deflection (1) between the massive and massless case? We shall see below that it does not.

2. Q: How do we identify the constants of motion $$E$$ and $$L$$ with the observables $$b$$ and $$v_0$$ at spatial infinity $$r=\infty$$? A: Note that \begin{align}r v_{\phi}~:=~ r^2\frac{d\phi}{dt}\quad\longrightarrow&\quad bv_0~=~h~=~\frac{L}{E}\cr &\quad\text{for}\quad r~\to~\infty, \end{align}\tag{3} and \begin{align}\frac{dr}{dt} \quad\longrightarrow&\quad v_0~=~c\frac{\sqrt{E^2-\epsilon}}{E}\cr &\quad\text{for}\quad r~\to~\infty.\end{align}\tag{4} Eq. (4) means that the energy constant is $$E=\gamma_0=\left(1-\frac{v_0^2}{c^2}\right)^{-1/2}$$ in the massive case, and it is undetermined in the massless case.

3. If we define the reciprocal radial coordinate $$u~:=~\frac{1}{r},\tag{5}$$ we get a 3rd-order polynomial$$^1$$ \begin{align} \left(\frac{du}{d\phi}\right)^2~=~&P(u)\cr ~:=~&\left(\frac{cE}{L}\right)^2 - n^{-1}\left(u^2+\frac{\epsilon c^2}{L^2}\right) \cr ~=~&r_s(u-u_+)(u-u_-)(u-u_0),\end{align}\tag{6} with 3 roots \begin{align}u_{\pm}~=~&\pm\frac{c}{L}\sqrt{E^2-\epsilon} ~+~\frac{r_s}{2}\left(\frac{cE}{L}\right)^2~+~{\cal O}(r_s^2)\cr ~=~&\pm \frac{1}{b}~+~\frac{GM}{h^2}~+~{\cal O}(M^2) ,\end{align} \tag{7} and
$$u_0~=~\frac{1}{r_s} +{\cal O}(r_s) .\tag{8}$$

4. During the scattering process the reciprocal radial coordinate $$u$$ goes from 0 to the root $$u_+$$ and then back again to 0. The half-angle is then \begin{align}\phi&~~~\stackrel{(6)}{=}~\int_0^{u_+} \! \frac{du}{\sqrt{P(u)}} \cr &~~~=~\int_0^{u_+} \! \frac{du}{\sqrt{(u_+-u)(u-u_-)\left(1-r_su\right)}} \cr &\stackrel{u=u_+x}{=}~\int_0^1 \! \frac{dx}{\sqrt{(1-x)(x+\alpha)}}\left(1+\beta x\right) +{\cal O}(r_s^2) \cr &~~~=~\beta\sqrt{\alpha}+(\alpha\beta+\beta+2)\arctan\frac{1}{\sqrt{\alpha}}+{\cal O}(r_s^2) \cr &~~~=~\frac{r_s }{2b}+2\arctan\left(1+\frac{r_s }{2b}\frac{c^2}{v_0^2}\right)+{\cal O}(r_s^2)\cr &~~~=~\frac{r_s }{2b}+2\left(\frac{\pi}{4}+\frac{r_s }{4b}\frac{c^2}{v_0^2}\right)+{\cal O}(r_s^2), \end{align}\tag{9} where we have defined \begin{align} \alpha~:=~&-\frac{u_-}{u_+}\cr ~=~&1-\frac{r_s}{L}\frac{E^2}{\sqrt{E^2-\epsilon}} +{\cal O}(r_s^2) \cr ~=~&1-\frac{r_s }{b}\frac{c^2}{v_0^2} +{\cal O}(r_s^2)\end{align} \tag{10} and \begin{align} \beta~:=~&\frac{r_s}{2}u_+ ~=~\frac{r_s}{2}\frac{\sqrt{E^2-\epsilon}}{L}+{\cal O}(r_s^2)\cr ~=~&\frac{r_s}{2b} +{\cal O}(r_s^2). \end{align}\tag{11} The constant $$\beta$$ vanishes in the Newtonian limit $$c\to \infty$$.

5. Finally, we can calculate the angle of deflection \begin{align}\theta ~=~&2\left(\phi-\frac{\pi}{2}\right)\cr ~\stackrel{(9)}{=}~&\frac{r_s}{b}\left(1 + \frac{c^2}{v_0^2}\right) +{\cal O}(r_s^2),\end{align}\tag{12} which is the sought-for formula (1). $$\Box$$

References:

1. Sean Carroll, Spacetime and Geometry: An Introduction to General Relativity, 2003; Section 5.4.

2. Sean Carroll, Lecture Notes on General Relativity, Chapter 7. The pdf file is available here.

3. R. Wald, GR, 1984; Section 6.3.

--

$$^1$$ In the Newtonian limit $$c\to \infty\leftrightarrow r_s \to 0$$ the 3rd-order polynomial (6) is replaced with a 2nd-order polynomial $$\left(\frac{du}{d\phi}\right)^2 ~=~(u_+-u)(u-u_-).\tag{13}$$ Differentiation leads to the Binet equation $$\frac{d^2u}{d\phi^2}+u ~=~\frac{r_s}{2}\left(\frac{cE}{L}\right)^2~=~\frac{GM}{h^2} .\tag{14}$$ The solutions are hyperbolas $$u~=~\frac{GM}{h^2}(1+ e\cos(\phi\!-\!\phi_0)), \tag{15}$$ where $$e>1$$ is eccentricity and $$\phi_0$$ is a phase offset.

• Related discussion: physics.stackexchange.com/q/246853/2451 Feb 24, 2019 at 22:39
• Notes for later: The scattering angle is minus the derivative of the radial action wrt. angular momentum. Aug 30, 2021 at 14:16

1) The bending of light rays is a general relativistic effect, not one due to Newton's law of gravity.

2) It's probably better to think about these things from a field perspective -- a distribution of mass-energy moves along, and it creates a gravitational field. Then, when things enter that field, they interact with it, and this changes their motion. These things might have their OWN gravitational field that can move the first things, or whatever else, but they are just interacting with the field, not the matter distribution that created the field.

I think what the OP was missing is the principle of the equivalence between mass and energy, as well as the fact that light rays do bend even in a vacuum, and even if that bending shows a curvature so subtle that it remains far beyond our perception without magnification equipment.

As pointed out by Viktor Toth at https://www.researchgate.net/post/Why_do_you_think_that_gravitational_lensing_is_due_to_time_dilation_Can_it_be_due_to_length_contraction , both gravitational time dilation and gravitational length contraction appear to have been equally involved in that deflection of light rays by gravitating objects, as verified during the 1919 eclipse mentioned by John Rennie: Some such deflection had been accepted as an effect of Newton's theory of gravity, and was exactly doubled by Einstein, leading to the 1st experimental confirmation of GR.

The most interesting thing about this, to me, is that the spatial aspect of the curvature involved appears to have been discovered more than a century after its temporal aspect: The shape of objects as familiar as the moon is suggestive of spatial curvature, but an understanding of time apparently held greater interest.

• My answer's among the least sophisticated, but I wanted to post it mainly to correct the misconception about light rays not bending, which could discourage interest in cosmological models whose local universes are closed. I'll be testing my preference for such models in subsequent questions.– Edouard Jan 22, 2021 at 17:22

If the mass of light is assumed to be strictly zero, Newton gravity would produce zero force. However the orbit of light is determined by acceleration, not force. For zero mass, acceleration is undefined. In the limit of photon mass going to zero the force goes to zero, but acceleration is of course independent of photon mass. One can therefore simply apply Newton acceleration to an object moving at speed c. This results in the value of Einstein's paper of 1911, which is half the GRT prediction and the experimental value. See https://en.m.wikipedia.org/wiki/Gravitational_lens #History.

• @PM2Ring Einstein indeed. Jan 22, 2021 at 3:20

It's just a simple concept according to Einstein's relativity when light travels through high gravation field or high mass containing object (i.e. same when a object has high mass means it can attract other objects of lesser mass) the photons present in the light gets attract towards the other object and we see light bending in the universe, but there is one thing is to note that photons are massless matters but in this case the object with higher mass attracts the object with lesser mass weather it is 0.


text:
# Find all identical data in a Column and filter it to another sheet

I have spent hours on this code, and truthfully need some better expert opinion.

Column A on Sheet 1 has dynamic list of data, typically IP address, but for this it is simply a number. There can be duplicates or not.

I need to find all identical data in column A, select it, and run specific code for it, then run the same code for each sets of identical data in A. My code is to find values in column C that matches the criteria of Less Than 4, or <4. Column C will only have values from 1 to 5. Goal is for each set of identical data in A, to then look at C and select any value in C that is only 1, 2, or 3, and NOT 4 or 5, and copy the entire row to another sheet when that is true.

My code works, kinda, but is slow, and does not account for if there is no data to copy.

Right now I use a sheet called Test to find unique data from A, then copy the identical data in A to a sheet called mm, filter the data, then copy only the filtered data to the sheet data. Contents in M are deleted on each loop and Test is deleted at the end of the code.

Please help me clean this up and make it faster. An image link is below if you want to see example data.

Credit goes to christodorov for getting me started as I used his base code.

Dim currentCell As Long
Dim numOfValues As Long

Sub filterNextResult()

' check to make sure there is at least 1 data point in column A on the temp sheet
If currentCell = 0 Then
Application.ScreenUpdating = False
Call createNewTemp
Application.ScreenUpdating = True
End If

' find the total number of unique data points we will be filtering by in column A of the temp sheet
If numOfAccounts = 0 Then
Application.ScreenUpdating = False
Call findNumOfValues
Application.ScreenUpdating = True
End If

Dim X As Integer
Dim lr As Long
Dim lrdata As Long
Dim Lastmm As Integer
lr = Sheets("mm").Cells(Rows.Count, "A").End(xlUp).Row + 1
lrdata = Sheets("data").Cells(Rows.Count, "A").End(xlUp).Row + 1
currentCell = 2
numOfValues = 21

On Error Resume Next
For X = 1 To numOfValues
With Sheet1.UsedRange
.AutoFilter 1, Worksheets("temp").Range("A" & currentCell).Value
Set filRange = .Offset(1).Resize(.Rows.Count - 1, 1).SpecialCells(xlCellTypeVisible)
If Not IsEmpty(filRange) Then
filRange.EntireRow.Copy Destination:=Sheets("mm").Range("A" & lr)
Worksheets("mm").Activate
Range("A1").Select
With Range("A1")
.AutoFilter Field:=3, Criteria1:="<4"
Lastmm = ActiveSheet.Cells(Rows.Count, 1).End(xlUp).Row
Range("A2:C" & Lastmm).Select
Selection.Copy
Worksheets("data").Activate
Range("A" & lrdata).PasteSpecial Paste:=xlPasteValues
Application.CutCopyMode = False
lrdata = Sheets("data").Cells(Rows.Count, "A").End(xlUp).Row + 1
Worksheets("mm").Activate
Range("A1").Select
Worksheets("mm").AutoFilterMode = False
Lastmm = ActiveSheet.Cells(Rows.Count, 1).End(xlUp).Row
Range("A2:C" & Lastmm).Select
Selection.Delete shift:=xlToLeft
End With

End If
currentCell = currentCell + 1

End With

Next X

Worksheets("temp").Delete

End Sub

'sub that will look for the number of values on the temp sheet column a
Private Sub findNumOfValues()
' count the number of non empty cells and assign that value (less 1 for the title in our case) to the numOfValues
numOfValues = Worksheets("temp").Range("A:A").Cells.SpecialCells(xlCellTypeConstants).Count
End Sub

Private Sub createNewTemp()

Sheet1.Range("A:C").Copy

' remove duplicates
Worksheets("temp").Range("A1").Select
With ActiveWorkbook.ActiveSheet
.Paste
End With

' check to make sure there are vlaues in the temp sheet
If Worksheets("temp").Range("A2").Value = "" Then
MsgBox "There are no filter values"
End
Else
currentCell = 2
End If

Sheet1.Activate
Sheet1.Range("A1").Select
Selection.AutoFilter

End Sub

Example of spreadsheet data before the process.

Credit to paul bica as he helped me. His code is below.

This will iterate through each unique value in column A, Sheet1 with these steps

Filter col A Apply the second filter to column C (< 4) If any rows are visible copies them to the first empty cell in Col A of Sheet2

Option Explicit

Public Sub FindIdenticalInALessThan4InC()
Const COL_A = 1
Const COL_C = 3
Const LESS_THAN_4 = "<4"
Dim ws1 As Worksheet, ws2 As Worksheet, lrWs1 As Long, lrWs2 As Long
Dim arrA As Variant, d As Object, i As Long, unique As Variant, maxRows As Long

Set ws1 = Sheet1:  Set ws2 = Sheet2                 'ws2 = CodeName for Sheets("mm")
maxRows = Rows.Count
If ws1.AutoFilterMode Then ws1.UsedRange.AutoFilter 'clear filters
lrWs1 = ws1.Cells(maxRows, "A").End(xlUp).Row + 1
lrWs2 = ws2.Cells(maxRows, "A").End(xlUp).Row + 1
If lrWs1 > 1 Then                                   'expects first row as headers
Set d = CreateObject("Scripting.Dictionary")
arrA = ws1.Range(ws1.Cells(1, COL_A), ws1.Cells(lrWs1, COL_A))
For i = 2 To lrWs1
d(arrA(i, 1)) = vbNullString                'get uniques from col A
Next
Application.ScreenUpdating = False
For Each unique In d
With ws1.UsedRange
.AutoFilter Field:=COL_A, Criteria1:=unique
.AutoFilter Field:=COL_C, Criteria1:=LESS_THAN_4, Operator:=xlAnd
If .Columns(1).SpecialCells(xlCellTypeVisible).CountLarge > 1 Then
.Offset(1).Resize(lrWs1 - 2, .Columns.Count).Copy ws2.Cells(lrWs2, "A")
lrWs2 = ws2.Cells(maxRows, "A").End(xlUp).Row + 1
End If
.AutoFilter
End With
Next
Application.ScreenUpdating = True
End If
End Sub

• You are honest. Sep 15 '17 at 7:38
• Plagiarism is bad. Sep 15 '17 at 16:27
• I really don't get it. You filter the list for every item in column A. But, why? Looking at your data, you would get row 1 and then row 6 and row 7 and.... But just applying the filter to column C will provide exactly the same list. That way you could copy paste the whole data in one step. I can't see what you are doing with the filtered data except from copying it... Sep 16 '17 at 5:28
• I filter row a for every unique item Then filter row c for every unique item from row a. Sep 17 '17 at 5:27